2013/10/03 by Long Wang, Yi-Zheng Fan · 6 citations
Computer Science · Mathematics · #Adjacency matrix #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Conjecture #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Line graph #Mathematics #Signature (topology) #math.CO #msc:05C50
paper · pdf · doi:10.1016/j.laa.2014.01.020
published in Linear Algebra and its Applications 448, 264-273 (Elsevier BV)
arxiv created 2013/10/03 · openalex publication_date 2014/02/06 · arxiv updated 2015/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 -c3(G)≤ s(G)≤ c5(G), where c3(G) and c5(G) respectively denote the number of cycles in G which have length 4k+3 and 4k+5 for some integers k ≥ 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.