Laplacian‎ ‎Coefficients of a‎ ‎Forest in Terms of the Number of Closed Walks in the Forest and its Line Graph

Document Type : Original Scientific Paper

Authors

‎Department of Pure Mathematics, ‎Faculty of Mathematical Sciences, ‎University of Kashan, ‎Kashan‎, ‎I‎. ‎R‎. ‎Iran

10.22052/mir.2024.255007.1467

Abstract

‎In this paper‎, ‎we deal with calculating the laplacian coefficients of a finite simple graph $G$ with the Laplacian polynomial $\psi(G,\lambda) = \sum_{k=0}^{n}(-1)^{n-k}c_k\lambda^k$‎. ‎We also explore the relationship between the number of closed walks in a graph and a series of its line graphs with the Laplacian coefficients‎. ‎Our objective is to find a way to determine the Laplacian coefficients using the number of closed walks in a graph and its line graph‎. ‎Specifically‎, ‎we have derived the Laplacian coefficients $c_{n-k}$ of a forest $F$ (where $1 \leq k \leq 6$) in terms of the number of closed walks in $F$ and its line graph‎.

Keywords

Main Subjects


[1] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17-20, https://doi.org/10.1021/ja01193a005.
[2] M. Randic, Novel molecular descriptor for structure-property studies, Chem. Phys. Lett. 211 (1993) 478-483, https://doi.org/10.1016/0009-2614(93)87094-J.
[3] D. J. Klein, I. Lukovits and I. Gutman, On the definition of the hyper-Wiener index for cycle-containing structures, J. Chem. Inf. Comput. Sci. 35 (1995) 50-52.
[4] I. Gutman and N. Trinajstic, Graph theory and molecular orbitals. Total \pi-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 ( 1972) 535-538, https://doi.org/10.1016/0009-2614(72)85099-1.
[5] I. Gutman, B. Ruscic, N. Trinajstic and C. F. Wilcox, Graph theory and molecular orbitals. XII. Acyclic polyenes, J. Chem. Phys. 62 (1975) 3399-3405, https://doi.org/10.1063/1.430994.
[6] I. Gutman and K. C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004) 83- 92.
[7] I. Gutman, E. Milovanovic and I. Milovanovic, Beyond the Zagreb indices, AKCE Int. J. Graphs Comb. 17 (2020) 74-85,
https://doi.org/10.1016/j.akcej.2018.05.002.
[8] S. Nikolic, G. Kovacevic, A. Milicevic and N. Trinajstic, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003) 113-124.
[9] B. Furtula and I. Gutman, A forgotten topological index, J. Math. Chem. 53 (2015) 1184-1190, https://doi.org/10.1007/s10910-015-0480-z.
[10] S. Zhang and H. Zhang, Unicyclic graphs with the first three smallest and largest first general Zagreb index, MATCH Commun. Math. Comput. Chem. 55 (2006) 427-438.
[11] A. Milicevic, S. Nikolic and N. Trinajstic, On reformulated Zagreb indices, Mol. Divers. 8 (2004) 393-399, https://doi.org/10.1023/B:MODI.0000047504.14261.2a.
[12] A. R. Ashrafi, M. Eliasi and A. Ghalavand, Laplacian coefficients and Zagreb indices of trees, Linear Multilinear Algebra 67 (2019) 1736-1749, https://doi.org/10.1080/03081087.2018.1469599.
[13] T. Doslic, On the Laplacian Szeged spectrum of paths, Iranian J. Math. Chem. 11 (2020) 57-63, https://doi.org/10.22052/IJMC.2020.215860.1480.
[14] M. Eliasi, The Laplacian spectrum of the generalized n-prism networks, Iranian J. Math. Chem. 15 (2024) 65-78.
[15] A. Ghalavand and A. R. Ashrafi, Laplacian coefficients of trees, Rad Hrvat. Akad. Znan. Umjet. Mat. Znan. 24 (2020) 1- 14.
[16] A. Ghalavand and A. R. Ashrafi, On the Laplacian coefficients of trees, Kragujev. J. Math. 49 (2024) 847-862, https://doi.org/10.46793/KgJMat2506.847G.
[17] A. Ghalavand and A. R. Ashrafi, Computing some Laplacian coefficients of forests, J. Appl. Math. (2022) p. 8199547,
https://doi.org/10.1155/2022/8199547.
[18] I. Gutman, Hyper-Wiener index and Laplacian spectrum, J. Serb. Chem. Soc. 68 (2003) 949-952, https://doi.org/10.2298/JSC0312949G.
[19] R. Merris, A survey of graph Laplacians, Linear and Multilinear Algebra 39 (1995) 19-31, https://doi.org/10.1080/03081089508818377.
[20] B. Mohar, The Laplacian spectrum of graphs, in: Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk (Eds), Graph Theory, Combinatorics, and Applications, Wiley, New York, (1991) pp. 871-898.
[21] C. S. Oliveira, N. M. M. de Abreu and S. Jurkiewicz, The characteristic polynomial of the Laplacian of graphs in (a; b)-linear classes, Linear Algebra Appl. 356 (2002) 113-121, https://doi.org/10.1016/S0024-3795(02)00357-9.
[22] W. Yan and Y.-N. Yeh, Connections between Wiener index and matchings, J. Math. Chem. 39 (2006) 389-399, https://doi.org/10.1007/s10910-005-9026-0.
[23] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs-Theory and Application, Academic Press, New York, 1980.