Back to Search Start Over

The signature of line graphs and power trees

Authors :
Wang, Long
Fan, Yi-Zheng
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

Subjects :
Mathematics - Combinatorics
05C50

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