Research ArticleOpen AccessGoogle Scholar indexed
The Laplacian Permanents and Laplacian Ratios of Trees
School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
- 1 School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
Applied Mathematics·Volume 16 (2025)·Pages 338–346·Published 11 April 2025·DOI10.4236/am.2025.164017
Copy link · social · email
Abstract
Brualdi and Goldwasser characterized the Laplacian permanents of trees. In this paper, we study the Laplacian permanents of trees. We characterize some Laplacian permanents of trees. The Laplacian ratio of G is the Laplacian permanent of G divided by the product of degrees of all vertices. In this paper, we obtain that for any n -vertex caterpillar tree T , there exists an n -vertex caterpillar tree C n such that π ( C n ) ≤ π ( T ) .
KeywordsLaplacian PermanentsLaplacian RatioTreeCaterpillar
- Valiant, L.G. (1979) The Complexity of Computing the Permanent. Theoretical Computer Science , 8, 189-201. https://doi.org/10.1016/0304-3975(79)90044-6
- Cvetkovic, D. (2005) Signless Laplacians and Line Graphs. Bulletin: Classe des sciences mathematiques et natturalles , 131, 85-92. https://doi.org/10.2298/bmat0530085c
- Cvetković, D., Rowlinson, P. and Simić, S.K. (2007) Signless Laplacians of Finite Graphs. Linear Algebra and its Applications , 423, 155-171. https://doi.org/10.1016/j.laa.2007.01.009
- Cvetković, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs. Johann Ambrosius Barth Verlag.
- Haemers, W.H. and Spence, E. (2004) Enumeration of Cospectral Graphs. European Journal of Combinatorics , 25, 199-211. https://doi.org/10.1016/s0195-6698(03)00100-8
- Cash, G.G. and Gutman, I. (1990) The Laplacian Permanental Polynomial: Formulas and Algorithms. MATCH Communications in Mathematical and in Computer Chemistry , 51, 129-136.
- Liu, S. (2019) On the (Signless) Laplacian Permanental Polynomials of Graphs. Graph Combin e , 35, 787-803.
- Brualdi, R.A. and Goldwasser, J.L. (1984) Permanent of the Laplacian Matrix of Trees and Bipartite Graphs. Discrete Mathematics , 48, 1-21. https://doi.org/10.1016/0012-365x(84)90127-4
- Goldwasser, J.L. (1986) Permanent of the Laplacian Matrix of Trees with a Given Matching. Discrete Mathematics , 61, 197-212. https://doi.org/10.1016/0012-365x(86)90091-9
- Cvetkovic, D., Rowlinson, P. and Simic, S. (2004) Spectral Generalizations of Line Graphs. Cambridge University Press. https://doi.org/10.1017/cbo9780511751752
- West, D.B. (2001) Introduction to Graph Theory. Prentice Hall.
- Geng, X., Hu, X. and Li, S. (2010) Further Results on Permanental Bounds for the Laplacian Matrix of Trees. Linear and Multilinear Algebra , 58, 571-587. https://doi.org/10.1080/03081080902765583
- Geng, X., Hu, S. and Li, S. (2014) Permanental Bounds of the Laplacian Matrix of Trees with Given Domination Number. Graphs and Combinatorics , 31, 1423-1436. https://doi.org/10.1007/s00373-014-1451-z
- Li, S. and Zhang, L. (2011) Permanental Bounds for the Signless Laplacian Matrix of a Unicyclic Graph with Diameter D. Graphs and Combinatorics , 28, 531-546. https://doi.org/10.1007/s00373-011-1057-7
- Li, S. and Zhang, L. (2011) Permanental Bounds for the Signless Laplacian Matrix of Bipartite Graphs and Unicyclic Graphs. Linear and Multilinear Algebra , 59, 145-158. https://doi.org/10.1080/03081080903261467