×

On the normalized Laplacian spectral radii of a graph and its line graph. (English) Zbl 1463.05356

Summary: Normalized Laplacian eigenvalues are very popular in spectral graph theory. The normalized Laplacian spectral radius \(\rho_1(G)\) of a graph \(G\) is the largest eigenvalue of normalized Laplacian matrix of \(G\). In this paper, we determine the extremal graph for the minimum normalized Laplacian spectral radii of nearly complete graphs. We present several lower bounds on \(\rho_1(G)\) in terms of graph parameters and characterize the extremal graphs. Still, there is no result on the normalized Laplacian eigenvalues of line graphs. Here, we obtain sharp lower bounds on the normalized Laplacian spectral radii of line graphs. Moreover, we compare \(\rho_1 (G)\) and \(\rho_1 (L_G)\) (\(L_G\) is the line graph of \(G\)) in some class of graphs as they are incomparable in the general case. Finally, we present a relation on the normalized Laplacian spectral radii of a graph and its line graph.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors

Software:

SageMath
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, JA; Murty, USR, Graph theory with applications (1976), New York: Macmillan Press, New York · Zbl 1226.05083
[2] Butler S (2008) Eigenvalues and structures of graphs. Ph.D. dissertation, University of California, San Diego
[3] Cavers M (2010) The normalized Laplacian matrix and general Randić index of graphs. Ph.D. dissertation, University of Regina · Zbl 1217.05138
[4] Cai, L.; Ellis, JA, Edge colouring line graphs of unicyclic graphs, Discrete Appl Math, 36, 75-82 (1992) · Zbl 0751.05037 · doi:10.1016/0166-218X(92)90206-P
[5] Chung, FK, Spectral graph theory (1997), Providence: American Mathematical Society, Providence · Zbl 0867.05046
[6] Das, KC; Sun, S., Extremal graph on normalized Laplacian spectral radius and energy, Electron J Linear Algebra, 29, 237-253 (2016) · doi:10.13001/1081-3810.3263
[7] Foster, RM, The average impedance of an electrical network, In Contributions to Applied Mechanics (Reissner Aniversary Volume), 333-340 (1949), Ann Arbor: Edwards Brothers, Ann Arbor · Zbl 0040.41801
[8] Guo, JM; Li, J.; Shiu, WC, Effects on the normalized Laplacian spectral radius of non-bipartite graphs under perturbation and their applications, Linear Multilinear Algebra, 64, 11, 2177-2187 (2016) · Zbl 1352.05113 · doi:10.1080/03081087.2016.1143912
[9] Guo, JM; Li, J.; Shiu, WC, The largest normalized Laplacian spectral radius of non-bipartite graphs, Bull Malays Math Sci Soc, 39, 1, 77-87 (2016) · Zbl 1339.05232 · doi:10.1007/s40840-015-0241-y
[10] Gutman, I.; Robbiano, M.; Martins, EA; Cardoso, DM; Medina, L.; Rojo, O., Energy of line graphs, Linear Algebra Appl, 433, 1312-1323 (2010) · Zbl 1194.05137 · doi:10.1016/j.laa.2010.05.009
[11] Kelmans, AK; Chelnokov, VM, A certain polynomial of a graph and graphs with an extremal number of trees, J Combin Theory B, 16, 197-214 (1974) · Zbl 0277.05104 · doi:10.1016/0095-8956(74)90065-3
[12] Klein, DJ; Randić, M., Resistance distance, J Math Chem, 12, 81-95 (1993) · doi:10.1007/BF01164627
[13] Li, J.; Guo, J-M; Shiu, WC, Bounds on normalized Laplacian eigenvalues of graphs, J Inequalities Appl, 316, 1-8 (2014) · Zbl 1332.05090
[14] Milovanović, EI; Matejić, MM; Milovanović, IŽ, On the normalized Laplacian spectral radius, Laplacian incidence energy and Kemeny’s constant, Linear Algebra Appl, 582, 181-196 (2019) · Zbl 1426.05105 · doi:10.1016/j.laa.2019.08.004
[15] Milovanović EI, Milovanović IŽ (2015) Remarks on bounds of normalized Laplacian Eigenvalues of graphs. arXiv:1506.05762v1 · Zbl 1363.15016
[16] Palacios, JL, Foster’s formulas via probability and the Kirchhoff Index, Methodol Comput Appl Probab, 6, 381-387 (2004) · doi:10.1023/B:MCAP.0000045086.76839.54
[17] Shi, L., Spectral radii of a graph and its line graph, Linear Algebra Appl, 422, 58-66 (2007) · Zbl 1111.05065 · doi:10.1016/j.laa.2006.08.030
[18] Schur, I., über eine Klasse von Mittelbildungen mit Anwendungen auf die Determinantentheorie, Sitzungsber Berl Math Ges, 22, 9-20 (1923) · JFM 49.0054.01
[19] Stein WA (2015) Sage mathematics software (version 6.8). The Sage Development Team. http://www.sagemath.org
[20] Stevanović, D.; Gutman, I.; Rehman, MU, On spectral radius and energy of complete multipartite graphs, Ars Math Contemp, 9, 109-113 (2015) · Zbl 1329.05201 · doi:10.26493/1855-3974.499.103
[21] Sun, S.; Das, KC, Normalized Laplacian eigenvalues with chromatic number and independence number of graphs, Linear Multilinear Algebra, 68, 1, 63-80 (2020) · Zbl 1429.05134 · doi:10.1080/03081087.2018.1498827
[22] Xu, K.; Das, KC; Zhang, XD, Ordering connected graphs by their Kirchhoff indices, Int J Comput Math, 93, 10, 1741-1755 (2016) · Zbl 1354.05084 · doi:10.1080/00207160.2015.1073722
[23] Yarahmadi, Z.; Ashrafi, A.; Diudea, M., Study of the bipartite edge frustration of graphs, Distance, symmetry, and topology in carbon nanomaterials (2016), New York: Springer, New York · Zbl 1360.05037
[24] Zhang, XD, On the Laplacian spectra of graphs, ARS Comb, 72, 191-198 (2004) · Zbl 1077.05062
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.