Spanning trees and even integer eigenvalues of graphs

DOI10.1016/J.DISC.2014.01.023zbMATH Open1284.05160arXiv1201.3221OpenAlexW2078007525MaRDI QIDQ2440944FDOQ2440944

Authors: E. Ghorbani 

Publication date: 20 March 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: For a graph $G$, let $L(G)$ and $Q(G)$ be the Laplacian and signless Laplacian matrices of $G$, respectively, and $au(G)$ be the number of spanning trees of $G$. We prove that if $G$ has an odd number of vertices and $au(G)$ is not divisible by $4$, then (i) $L(G)$ has no even integer eigenvalue, (ii) $Q(G)$ has no integer eigenvalue $lambdaequiv2pmod4$, and (iii) $Q(G)$ has at most one eigenvalue $lambdaequiv0pmod4$ 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 $au(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 $au(G)$ is divisible by $4$. As a very special case of this result, a conjecture by Zhou et al. [On the nullity of connected graphs with least eigenvalue at least $-2$, Appl. Anal. Discrete Math. 7 (2013), 250--261] on the nullity of adjacency matrices of the line graphs of unicyclic graphs follows.

Full work available at URL: https://arxiv.org/abs/1201.3221

Recommendations

• An analog of matrix tree theorem for signless Laplacians
• Trees with Four and Five Distinct Signless Laplacian Eigenvalues
• scientific article; zbMATH DE number 1484041
• A note on the integer eigenvalues of the Laplacian matrix of a balanced binary tree
• On the main signless Laplacian eigenvalues of a graph

zbMATH Keywords

spanning treesLaplacianline graphsignless Laplacianunicyclic graphnullityeven integer eigenvalue

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Paths and cycles (05C38)

Cites Work

• Signless Laplacians of finite graphs
• An introduction to the theory of graph spectra
• On the nullity of line graphs of trees
• A certain polynomial of a graph and graphs with an extremal number of trees
• An interrelation between line graphs, eigenvalues, and matroids
• On a conjecture concerning spanning tree invariants and loop systems
• Title not available (Why is that?)
• On the nullity of connected graphs with least eigenvalue at least -2
• Title not available (Why is that?)

Cited In (4)

• An analog of matrix tree theorem for signless Laplacians
• Title not available (Why is that?)
• Graphs with least eigenvalue \(-2\): ten years on
• Tree-width, clique-minors, and eigenvalues.

This page was built for publication: Spanning trees and even integer eigenvalues of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2440944)