Spanning trees and even integer eigenvalues of graphs

作者：Ghorbani Ebrahim^*

来源：Discrete Mathematics, 2014, 324: 62-67.

DOI：10.1016/j.disc.2014.01.023

• Spanning trees
• Even integer eigenvalue
• Line graph
• Nullity
• Signless Laplacian
• Laplacian
• Unicyclic graph

For a graph G, let L(G) and Q(G) be the Laplacian and signless Laplacian matrices of G, respectively, and tau(G) be the number of spanning trees of G. We prove that if G has an odd number of vertices and tau(G) is not divisible by 4, then (i) L(G) has no even integer eigenvalue, (ii) Q(G) has no integer eigenvalue lambda 2 (mod 4), and (iii) Q(G) has at most one eigenvalue lambda 0 (mod 4) and such an eigenvalue is simple. As a consequence, we extend previous results by Gutman and Sciriha and by Bapat on the nullity of adjacency matrices of the line graphs. We also show that if tau(G) = 2(t)s with s odd, then the multiplicity of any even integer eigenvalue of Q(G) is at most t + 1. Among other things, we prove that if L(G) or Q(G) has an even integer eigenvalue of multiplicity at least 2, then r (G) is divisible by 4. As a very special case of this result, a conjecture by Zhou et al. (2013) on the nullity of adjacency matrices of the line graphs of unicyclic graphs follows.

• 出版日期2014-6-6