×

On a conjecture of Laplacian energy of trees. (English) Zbl 1493.05191

Summary: Let \(G\) be a simple graph with \(n\) vertices, \(m\) edges having Laplacian eigenvalues \(\mu_1, \mu_2,\dots, \mu_{n - 1}, \mu_n=0\). The Laplacian energy LE \((G)\) is defined as LE \((G)= \sum_{i = 1}^n| \mu_i- \overline{d}|\), where \(\overline{d}=\frac{2 m}{n}\) is the average degree of \(G\). Radenković and Gutman conjectured that among all trees of order \(n\), the path graph \(P_n\) has the smallest Laplacian energy. Let \(\mathcal{T}_n(d)\) be the family of trees of order \(n\) having diameter \(d\). In this paper, we show that Laplacian energy of any tree \(T\in \mathcal{T}_n(4)\) is greater than the Laplacian energy of \(P_n\), thereby proving the conjecture for all trees of diameter \(4\). We also show the truth of conjecture for all trees with number of non-pendent vertices at most \(\frac{9 n}{2 5}-2\). Further, we give some sufficient conditions for the conjecture to hold for a tree of order \(n\).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C12 Distance in graphs
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brouwer, A. E. and Haemers, W. H., A lower bound on the Laplacian eigenvalues of a graph-proof of a conjecture by Guo, Linear Algebra Appl.429 (2008) 2131-2135. · Zbl 1144.05315
[2] Cvetković, D. M., Rowlison, P. and Simić, S., An Introduction to the Theory of Graph Spectra, , Vol. 75, London Mathematical Society Student Text (Cambridge University Press, UK, 2010). · Zbl 1211.05002
[3] Chang, A. and Deng, B., On the Laplacian energy of trees with perfect matchings, MATCH Comm. Math. Comp. Chem.68 (2012) 767-776. · Zbl 1289.05272
[4] Faria, I., Permanental roots and the star degree of a graph, Linear Algebra Appl.64 (1985) 255-265. · Zbl 0559.05041
[5] Fricke, G. H., Hedetniemi, S. T., Jacobs, D. P. and Trevisan, V., Reducing the adjacency matrix of a tree, Electron. J. Linear Algebra1 (1996) 34-43. · Zbl 0886.05048
[6] Fritscher, E., Hoppen, C., Rocha, I. and Trevisan, V., On the sum of the Laplacian eigenvalues of a tree, Linear Algebra Appl.435 (2011) 371-399. · Zbl 1226.05154
[7] Gutman, I., Acyclic system with extremal Hŭckel-electron energy, Theoret. Chim. Acta.45 (1977) 79-87.
[8] Gutman, I., The energy of a graph, Ber. Math. Statist. Sekt. Forschungsz. Graz.103 (1978) 1-22. · Zbl 0402.05040
[9] Gutman, I. and Zhou, B., Laplacian energy of a graph, Linear Algebra Appl.414 (2006) 29-37. · Zbl 1092.05045
[10] Grone, R., Eigenvalues and the degree sequences of graphs, Linear Multilinear Algebra391-392 (1995) 133-136. · Zbl 0831.05047
[11] Grone, R., Merris, R. and Sunder, V. S., The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl.11 (1990) 218-238. · Zbl 0733.05060
[12] Ganie, H. A. and Chat, B. A., Bounds for the energy of weighted graphs, Discrete Appl. Math.268 (2019) 91-101. · Zbl 1419.05098
[13] Ganie, H. A., Chat, B. A. and Pirzada, S., On the signless Laplacian energy of a graph and energy of line graph, Linear Algebra Appl.544 (2018) 306-324. · Zbl 1388.05114
[14] Ganie, H. A., Pirzada, S., Rather, B. A. and Trevisan, V., Further developments on Brouwer’s conjecture for the sum of Laplacian eigenvalues of graphs, Linear Algebra Appl.588 (2020) 1-18. · Zbl 1437.05139
[15] Ganie, H. A., Pirzada, S. and Trevisan, V., On the sum of \(k\) largest Laplacian eigenvalues of a graph and clique number, Mediterranean J. Math.18 (2021) 1-13. · Zbl 1456.05104
[16] Ganie, H. A., Pirzada, S., Rather, B. A. and Ul Shaban, R., On Laplacian eigenvalues of graphs and Brouwer’s conjecture, J. Ramanujan Math. Soc.36(1) (2021) 1-9. · Zbl 1469.05103
[17] Ganie, H. A., Pirzada, S., Rezwan and Li, X., Upper bounds for the sum of Laplacian eigenvalues of a graph and Brouwer’s conjecture, Discrete Math. Algorithms Appl.11(2) (2019) 195008 (15 p.). · Zbl 1410.05125
[18] Horn, R. and Johnson, C., Matrix Analysis (Cambridge University Press, 2012).
[19] Jacobs, D. P. and Trevisan, V., Locating the eigenvalues of a tree, Linear Algebra Appl.434 (2011) 81-88. · Zbl 1231.05167
[20] Jacobs, D. P. and Trevisan, V., Constructing the characteristic polynomial of a tree’s adjacency matrix, Congr. Mumer.134 (1998) 139-145. · Zbl 0953.05046
[21] Mojallal, S. A. and Hansen, P., On the difference of energies of a graph and its complement graph, Linear Algebra Appl.595 (2020) 1-12. · Zbl 1454.05071
[22] Monsalve, J. and Rada, J., Oriented bipartite graphs with minimal trace norm, Linear Multilinear Algebra67 (2019) 1121-1131. · Zbl 1411.05172
[23] Nikiforov, V., Beyond graph energy: Norms of graphs and matrices, Linear Algebra Appl.506 (2016) 82-138. · Zbl 1344.05089
[24] Pirzada, S. and Ganie, H. A., On the Laplacian eigenvalues of a graph and Laplacian energy, Linear Algebra Appl.486 (2015) 454-468. · Zbl 1327.05157
[25] Pirzada, S., An Introduction to Graph Theory (Universities Press, Orient BlackSwan, Hyderabad, 2012).
[26] Pirzada, S., Ganie, H. A., Rather, B. A. and Shaban, R. U., On generalized distance energy of graphs, Linear Algebra Appl.603 (2020) 1-19. · Zbl 1484.05137
[27] Pirzada, S. and Khan, S., On distance Laplacian spectral radius and chromatic number of graphs, Linear Algebra Appl.625 (2021) 44-54. · Zbl 1465.05105
[28] Ul Rahman, J., Ali, U. and Rehman, M., Laplacian energy of diameter \(4\) trees, J. Disc. Math. Sci. Cryp. (2019). https://doi.org/10.1080/09720529.2019.1670943 · Zbl 1483.05098
[29] Radenković, S. and Gutman, I., Total \(\pi \)-electron energy and Laplacian energy: How far the analogy goes?J. Serb. Chem. Soc.72 (2007) 1343-1350.
[30] Sin, C., On the number of Laplacian eigenvalues of tree less than the average degree, Discrete Math.343 (2020) 111986. · Zbl 1445.05063
[31] Trevisan, V., Carvalho, J. B., Del Vecchio, R. R. and Vinagre, C. M., Laplacian energy of diameter \(3\) trees, App. Math. Lett.24 (2011) 918-923. · Zbl 1216.05010
[32] Zhou, L., Zhou, B. and Du, Z., On the number of Laplacian eigenvalues of tree smaller than two, Taiwanese J. Math.19 (2015) 65-75. · Zbl 1357.05098
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.