×

Line graphs of trees with the largest eigenvalue multiplicity. (English) Zbl 1525.05122

Given a tree \(T\) with \(p\geq 3\) pendant edges, the authors prove that the multiplicity of any eigenvalue of the line graph of \(T\) is less than \(p\). In addition, the line graphs for which there is an eigenvalue with multiplicity \(p-1\) are fully characterized.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrade, E.; Cardoso, D. M.; Pastsén, G.; Rojo, O., On the Faria’s inequality for the Laplacian and signless Laplacian spectra: a unified approach, Linear Algebra Appl., 472, 81-86 (2015) · Zbl 1307.05136
[2] Atkins, P. W.; de Paula, J., Physical Chemistry (2006), Oxford University Press
[3] Belardo, F.; Brunetti, M.; Ciampella, A., On the multiplicity of α as an \(A_\alpha(\operatorname{\Gamma})\)-eigenvalue of signed graphs with pendant vertices, Discrete Math., 342, 2223-2233 (2019) · Zbl 1418.05070
[4] Bell, F. K.; Rowlinson, P., On the multiplicities of graph eigenvalues, Bull. Lond. Math. Soc., 35, 401-408 (2003) · Zbl 1023.05097
[5] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (2012), Springer: Springer New York · Zbl 1231.05001
[6] Bu, C.; Zhang, X.; Zhou, J., A note on the multiplicities of graph eigenvalues, Linear Algebra Appl., 442, 69-74 (2014) · Zbl 1283.05163
[7] Cardoso, D. M.; Pastén, G.; Rojo, O., On the multiplicity of α as an eigenvalue of \(A_\alpha(G)\) of graphs with pendant vertices, Linear Algebra Appl., 552, 52-70 (2018) · Zbl 1391.05282
[8] Chang, G. J.; Huang, L. H.; Yeh, H. G., A characterization of graphs with rank 4, Linear Algebra Appl., 434, 1793-1798 (2011) · Zbl 1216.05071
[9] Chang, G. J.; Huang, L. H.; Yeh, H. G., A characterization of graphs with rank 5, Linear Algebra Appl., 436, 4241-4250 (2012) · Zbl 1241.05062
[10] Cheng, B.; Liu, B., On the nullity of graphs, Electron. J. Linear Algebra, 16, 60-67 (2007) · Zbl 1142.05336
[11] Cvetković, D.; Gutman, I., The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesn. (Beogr.), 9, 141-150 (1972) · Zbl 0263.05125
[12] Fan, Y. Z.; Qian, K. S., On the nullity of bipartite graphs, Linear Algebra Appl., 430, 2943-2949 (2009) · Zbl 1169.05346
[13] Faria, I., Permanental roots and the star degree of a graph, Linear Algebra Appl., 64, 255-265 (1985) · Zbl 0559.05041
[14] Fiorini, S.; Gutman, I.; Sciriha, I., Trees with maximum nullity, Linear Algebra Appl., 397, 245-251 (2005) · Zbl 1068.05015
[15] Gong, S.; Xu, G., On the nullity of a graph with cut-points, Linear Algebra Appl., 436, 135-142 (2012) · Zbl 1243.05147
[16] Gong, S.; Xu, G.; Zhang, W., 4-regular oriented graphs with optimum skew energies, Eur. J. Comb., 36, 77-85 (2014) · Zbl 1284.05161
[17] Grone, R.; Merris, R.; Sunder, V. S., The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 11, 218-238 (1990) · Zbl 0733.05060
[18] Grone, R.; Merris, R., The Laplacian spectrum of graph II, SIAM J. Discrete Math., 7, 221-229 (1994) · Zbl 0795.05092
[19] Guo, J.; Yan, W.; Yeh, Y., On the nullity and the matching number of unicyclic graphs, Linear Algebra Appl., 431, 1293-1301 (2009) · Zbl 1238.05160
[20] Guo, J., The kth Laplacian eigenvalue of a tree, J. Graph Theory, 3, 51-57 (2006) · Zbl 1110.05061
[21] Gutman, I.; Sciriha, I., On the nullity of line graphs of trees, Discrete Math., 232, 35-45 (2001) · Zbl 0971.05070
[22] Hedetniemi, S. T.; Jacobs, D. P.; Trevisan, V., Domination number and Laplacian eigenvalue distribution, Eur. J. Comb., 53, 66-71 (2016) · Zbl 1328.05141
[23] Johnson, C. R.; Sutton, B. D., Eigenvalue multiplicities, and eigenvector components, SIAM J. Matrix Anal. Appl., 26, 390-399 (2004) · Zbl 1083.15015
[24] Johnson, C. R.; Leal Duarte, A.; Saiago, C. M., The Parter-Wiener theorem: refinement and generalization, SIAM J. Matrix Anal. Appl., 25, 352-361 (2003) · Zbl 1067.15003
[25] Li, W.; Chang, A., On the trees with maximum nullity, MATCH Commun. Math. Comput. Chem., 56, 501-508 (2006) · Zbl 1121.05072
[26] Li, H. H.; Su, L.; Sun, H. X., On bipartite graphs which attain minimum rank among bipartite graphs with given diameter, Electron. J. Algebra, 23, 137-150 (2012) · Zbl 1252.05124
[27] Ma, X.; Wong, D.; Tian, F., 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) · Zbl 1346.05144
[28] Ma, X.; Wong, D.; Zhu, M., The positive and the negative inertia index of line graphs of trees, Linear Algebra Appl., 439, 3120-3128 (2013) · Zbl 1282.05137
[29] Omidi, G. R., On the nullity of bipartite graphs, Graphs Comb., 25, 111-114 (2009) · Zbl 1194.05092
[30] Rowlinson, P., On multiple eigenvalues of trees, Linear Algebra Appl., 432, 3007-3011 (2010) · Zbl 1195.05044
[31] Rowlinson, P., On eigenvalue multiplicity and the girth of a graph, Linear Algebra Appl., 435, 2375-2381 (2011) · Zbl 1222.05179
[32] Song, Y.; Song, X.; Tam, B., A characterization of graphs with nullity \(| V(G) | - 2 m(G) + 2 c(G)\), Linear Algebra Appl., 465, 363-375 (2015) · Zbl 1303.05158
[33] Song, Y.; Song, X.; Zhang, C., An upper bound for the nullity of a bipartite graph in terms of its maximum degree, Linear Multilinear Algebra, 64, 1107-1112 (2016) · Zbl 1335.05115
[34] Tan, X.; Liu, B., On the nullity of unicyclic graphs, Linear Algebra Appl., 408, 212-220 (2005) · Zbl 1073.05044
[35] Wong, D.; Ma, X.; Tian, F., Relation between the skew-rank of an oriented graph and the rank of its underlying graph, Eur. J. Comb., 54, 76-86 (2016) · Zbl 1331.05097
[36] Wong, D.; Zhou, Q.; Tian, F., On the multiplicity of eigenvalues of trees, Linear Algebra Appl., 593, 180-187 (2020) · Zbl 1437.05154
[37] Zhou, Q.; Wong, D.; Sun, D., An upper bound of the nullity of a graph in terms of order and maximum degree, Linear Algebra Appl., 555, 314-320 (2018) · Zbl 1395.05105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.