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$, $\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. [1] A.T. Amin, L.H. Clark and P.J. Slater, Parity dimension for graphs, Discrete Math. 187 (1-3), 1-17, 1998.
2. [2] A.T. Amin and P.J. Slater, Neighborhood domination with parity restrictions in graphs, In Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1992), volume 91, pages 19-30, 1992.
3. [3] A.T. Amin and P.J. Slater, All parity realizable trees, J. Combin. Math. Combin. Comput. 20, 53-63, 1996.
4. [4] A.T. Amin, P.J. Slater and G.H. Zhang, Parity dimension for graphs -a linear algebraic approach, Linear Multilinear Algebra 50 (4), 327-342, 2002.
5. [5] L.E. Ballard, E.L. Budge and D.R. Stephenson, Lights out for graphs related to one another by constructions, Involve 12 (2), 181-201, 2019.
6. [6] S. Chang, A. Chang and Y. Zheng, The leaf-free graphs with nullity $2c(G)-1$, Discrete Appl. Math. 277, 44-54, 2020.
7. [7] G.J. Chang, L.H. Huang and H.G. Yeh, A characterization of graphs with rank 4, Linear Algebra Appl. 434 (8), 1793-1798, 2011.
8. [8] G.J. Chang, L.H. Huang and H.G. Yeh, A characterization of graphs with rank 5, Linear Algebra Appl. 436 (11), 4241-4250, 2012.

9. [9] S. Chang, B.S. Tam, J. Li and Y. Zheng, Graphs G with nullity $2c(G) + p(G) - 1$, Discrete Appl. Math. 311, 38-58, 2022.
10. [10] C. Chen, J. Huang and S. Li, On the relation between the H-rank of a mixed graph and the matching number of its underlying graph, Linear Multilinear Algebra 66 (9), 1853-1869, 2018.
11. [11] B. Cheng and B. Liu, On the nullity of tricyclic graphs, Linear Algebra Appl. 434 (8), 1799-1810, 2011.
12. [12] Y.Z. Fan, Y. Wang and Y. Wang, A note on the nullity of unicyclic signed graphs, Linear Algebra Appl. 438 (3), 1193-1200, 2013.
13. [13] I. Faria, Permanental roots and the star degree of a graph, Linear Algebra Appl. 64, 255-265, 1985.
14. [14] S. Fiorini, I. Gutman and I. Sciriha. Trees with maximum nullity, Linear Algebra Appl. 397, 245-251, 2005.
15. [15] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2001.
16. [16] S.C. Gong, Y.Z. Fan and Z.X. Yin, On the nullity of graphs with pendant trees, Linear Algebra Appl. 433 (7), 1374-1380, 2010.
17. [17] S.C. Gong and G.H. Xu, On the nullity of a graph with cut-points, Linear Algebra Appl. 436 (1), 135-142, 2012.
18. [18] J.M. Guo, W. Yan and Y.N. Yeh, On the nullity and the matching number of unicyclic graphs, Linear Algebra Appl. 431 (8), 1293-1301, 2009.
19. [19] I. Gutman and I. Sciriha, On the nullity of line graphs of trees, Discrete Math. 232(1- 3), 35-45, 2001.
20. [20] S. Hu, T. Xuezhong and B. Liu, On the nullity of bicyclic graphs, Linear Algebra Appl. 429 (7), 1387-1391, 2008.
21. [21] W. Li and A. Chang, On the trees with maximum nullity, MATCH Commun. Math. Comput. Chem. 56 (3), 501-508, 2006.
22. [22] H.H. Li, Y.Z. Fan and L. Su, On the nullity of the line graph of unicyclic graph with depth one, Linear Algebra Appl. 437 (8), 2038-2055, 2012.
23. [23] H.H. Li, L. Su and H.X. Sun, On bipartite graphs which attain minimum rank among bipartite graphs with a given diameter, Electron. J. Linear Algebra 23, 137-150, 2012.
24. [24] S. Li and W. Wei, The multiplicity of an $A_\alpha$-eigenvalue: a unified approach for mixed graphs and complex unit gain graphs, Discrete Math. 343 (8), 111916, 19, 2020.
25. [25] W. Luo, J. Huang and S. Li, On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph, Linear Algebra Appl. 554, 205-223, 2018.
26. [26] Y. Lu, L. Wang and Q. Zhou, The rank of a signed graph in terms of the rank of its underlying graph, Linear Algebra Appl. 538, 166-186, 2018.
27. [27] Y. Lu, L. Wang and Q. Zhou, Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph, Filomat 32 (4), 1303-1312, 2018.
28. [28] X. Ma, D. Wong and F. Tian, Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices, Discrete Appl. Math. 215, 171-176, 2016.
29. [29] X. Ma, D. Wong and F. Tian, Skew-rank of an oriented graph in terms of matching number, Linear Algebra Appl. 495, 242-255, 2016.
30. [30] V. Nikiforov, Merging the A- and Q-spectral theories, Appl. Anal. Discrete Math. 11 (1), 81-107, 2017.
31. [31] G.R. Omidi, On the nullity of bipartite graphs, Graphs Combin. 25 (1), 111-114, 2009.
32. [32] I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181 (1-3), 193-211, 1998.
33. [33] Y. Song, X. Song and B.S. Tam, A characterization of graphs G with nullity $|V(G)|-2m(G)+2c(G)$, Linear Algebra Appl. 465, 363-375, 2015.
34. [34] Y. Song, X. Song and M. Zhang, An upper bound for the nullity of a bipartite graph in terms of its maximum degree, Linear Multilinear Algebra 64 (6), 1107-1112, 2016.
35. [35] L. Wang, L. Wei and Y. Jin, The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices, Linear Algebra Appl. 584, 257-266, 2020.
36. [36] L. Wang and D. Wong, Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank, Discrete Appl. Math. 166, 276-281, 2014.
37. [37] X. Wang, D. Wong, L. Wei and F. Tian, On the multiplicity of –1 as an eigenvalue of a tree with given number of pendant vertices, Linear Multilinear Algebra 70 (17), 3345-3353, 2022.
38. [38] D. Wong, X. Ma and F. Tian, Relation between the skew-rank of an oriented graph and the rank of its underlying graph, Eur. J. Comb. 54, 76-86, 2016.
39. [39] D. Wong, Q. Zhou and F. Tian, Nullity and singularity of a graph in which every block is a cycle. Discrete Math. 345 (6), Paper No. 112851, 8, 2022.
40. [40] D. Wong, M. Zhu and W. Lv, A characterization of long graphs of arbitrary rank, Linear Algebra Appl. 438 (3), 1347-1355, 2013.
41. [41] F. Xu, D. Wong and F. Tian, On the multiplicity of $\alpha$ as an eigenvalue of the $A_\alpha$ matrix of a graph in terms of the number of pendant vertices, Linear Algebra Appl. 594, 193-204, 2020.
42. [42] T. Xuezhong and B. Liu, On the nullity of unicyclic graphs, Linear Algebra Appl. 408, 212-220, 2005.
43. [43] J. Zhou, L. Sun, H. Yao and C. Bu, On the nullity of connected graphs with least eigenvalue at least −2, Appl. Anal. Discrete Math. 7 (2), 250-261, 2013.
44. [44] Q. Zhou and D. Wong, Graphs with eigenvalue −1 of multiplicity $2\theta(G) + \rho(G) - 1$, Linear Algebra Appl. 645, 137-152, 2022.
45. [45] Q. Zhou, D. Wong and D. Sun, An upper bound of the nullity of a graph in terms of order and maximum degree, Linear Algebra Appl. 555, 314-320, 2018.