Bounding the multiplicities of eigenvalues of graph matrices in terms of circuit rank

Year 2025, Early Access, 1 - 10

Ahmet Batal

https://doi.org/10.15672/hujms.1474122

Abstract

Let $G$ be a simple undirected graph, $\theta(G)$ be the circuit rank of $G$, $\eta_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 $m_M(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 $m_{A_{\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 $m_A(G,\lambda)$ (and later $m_{A_\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 $\eta_A(G_c)\leq \theta(G_c)+1$, where $G_c$ 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 $\eta_A(G_c)\leq 1$ when every block of the cactus is an odd cycle. This also aligns with a special case of our bound.

Keywords

multiplicity , nullity , 2-nullity , bicycle space , cycle space , circuit rank

References

• [1] A.T. Amin, L.H. Clark and P.J. Slater, Parity dimension for graphs, Discrete Math. 187 (1-3), 1-17, 1998.