Back to Search
Start Over
The signature of line graphs and power trees
- Source :
- Linear Algebra and its Applications, 2014, 448, 264-273
- Publication Year :
- 2013
-
Abstract
- Let $G$ be a graph and let $A(G)$ be the adjacency matrix of $G$. The signature $s(G)$ of $G$ is the difference between the positive inertia index and the negative inertia index of $A(G)$. Ma et al. [Positive and negative inertia index of a graph, Linear Algebra and its Applications 438(2013)331-341] conjectured that $-c_3(G)\leq s(G)\leq c_5(G),$ where $c_3(G)$ and $c_5(G)$ respectively denote the number of cycles in $G$ which have length $4k+3$ and $4k+5$ for some integers $k \ge 0$, and proved the conjecture holds for trees, unicyclic or bicyclic graphs. It is known that $s(G)=0$ if $G$ is bipartite, and the signature is closely related to the odd cycles or nonbipartiteness of a graph from the existed results. In this paper we show that the conjecture holds for the line graph and power trees.
- Subjects :
- Mathematics - Combinatorics
05C50
Subjects
Details
- Database :
- arXiv
- Journal :
- Linear Algebra and its Applications, 2014, 448, 264-273
- Publication Type :
- Report
- Accession number :
- edsarx.1310.1003
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.laa.2014.01.020