Bounding the Multiplicities of Eigenvalues of Graph Matrices in Terms of Circuit Rank

Abstract

Let G be a simple undirected graph, theta(G) be the circuit rank of G, M(G) be the nullity of a graph matrix M(G), and m(M)(G, lambda) be the multiplicity of eigenvalue lambda of M(G). In the case M(G) is the adjacency matrix A(G) (the Laplacian matrix L(G), or the signless Laplacian matrix Q(G)) we find bounds to mM(G, lambda) in terms of theta(G), when lambda is an integer (even integer, respectively). We also demonstrate that when alpha and lambda are rational numbers, similar bounds can be obtained for mA alpha (G, lambda), where A alpha (G) is the generalized adjacency matrix of G. Distinctively, our bounds involve only theta(G), not a multiple of it. Previous bounds for mA(G, lambda) (and later mA(alpha)(G, lambda)) in terms of the circuit rank have all included 2 theta(G) with the sole exception of the case lambda = 0. Wong et al. (2022) showed that A(Gc) < theta(G(c)) + 1, where Gc is a connected cactus whose blocks are even cycles. Our result, in particular, generalizes and extends this result to the multiplicity of any even eigenvalue of A(G) of any even connected graph G, as well as to any even eigenvalue of L(G) and Q(G) for any connected graph G. They also showed that A(G(c)) < 1 when every block of the cactus is an odd cycle. This also aligns with a special case of our bound.