Abstract
Let μ(T) and Δ(T) denote the Laplacian spectral radius and the maximum degree of a tree T, respectively. Denote by \({\mathcal{T}_{2m}}\) the set of trees with perfect matchings on 2m vertices. In this paper, we show that for any \({T_1, T_2\in\mathcal{T}_{2m}}\) , if Δ(T 1) > Δ(T 2) and \({\Delta(T_1)\geq \lceil\frac{m}{2}\rceil+2}\) , then μ(T 1) > μ(T 2). By using this result, the first 20th largest trees in \({\mathcal{T}_{2m}}\) according to their Laplacian spectral radius are ordered. We also characterize the tree which alone minimizes (resp., maximizes) the Laplacian spectral radius among all the trees in \({\mathcal{T}_{2m}}\) with an arbitrary fixed maximum degree c (resp., when \({c \geq \lceil\frac{m}{2}\rceil + 1}\)).
Similar content being viewed by others
References
Merris R.: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197(198), 143–176 (1994)
Gutman I.: The star is the tree with greatest Laplacian eigenvalue. Kragujevac J. Math. 24, 61–65 (2002)
Petrović M., Gutman I.: The path is the tree with smallest greatest Laplacian eigenvalue. Kragujevac J. Math. 24, 67–70 (2002)
Guo J.M.: On the Laplacian sepectral radius of a tree. Linear Algebra Appl. 368, 379–385 (2003)
Yu A.M., Lu M.: Laplacian spectral radius of trees with given maximum degree. Linear Algebra Appl. 429, 1962–1969 (2008)
Hong Y., Zhang X.D.: Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrix of trees. Discrete Math. 296, 187–197 (2005)
Guo J.M.: On the Laplacian spectral radius of trees with fixed diameter. Linear Algebra Appl. 419, 618–629 (2006)
Zhang X.D.: The Laplacian spectral radii of trees with degree sequences. Discrete Math. 308, 3143–3150 (2008)
Yuan X.Y., Shan H.Y., Liu Y.: On the Laplacian spectral radii of trees. Discrete Math. 309, 4241–4246 (2009)
Yuan X.Y., Shao J.Y., He C.X.: On the Laplacian spectral radii of trees with perfect matchings. J. Math. Chem. 46, 65–85 (2009)
Fang M.: On Laplacian radii of trees with perfect matching (in Chinese). J. Tongji Univ. (Nat. Sci.) 35(11), 1568–1571 (2007)
Yuan X.Y., Wu B.F., Xiao E.L.: The modifications of trees and the Laplacian spectrum (in Chinese). J. East China Norm. Univ. (Nat. Sci.) 2, 13–18 (2004)
Guo J.M.: The effect on the Laplacian spectral radius of a graph by adding or grafting edges. Linear Algebra Appl. 413, 59–71 (2006)
Guo J.M.: On the second largest Laplacian eigenvalue of trees. Linear Algebra Appl. 404, 251–261 (2005)
Li J.S., Zhang X.D.: On the Laplacian eigenvalues of a graph. Linear Algebra Appl. 285, 305–307 (1998)
Chang A.: On the largest eigenvalue of a tree with perfect matchings. Discrete Math. 269, 45–63 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by NSFC(10831001).
Rights and permissions
About this article
Cite this article
Chen, X., Qian, J. Laplacian Spectral Radius and Maximum Degree of Trees with Perfect Matchings. Graphs and Combinatorics 29, 1249–1257 (2013). https://doi.org/10.1007/s00373-012-1205-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-012-1205-8