Ordering trees with nearly perfect matchings by algebraic connectivity

Abstract

Let T _2k+1 be the set of trees on 2k+1 vertices with nearly perfect matchings and α(T) be the algebraic connectivity of a tree T. The authors determine the largest twelve values of the algebraic connectivity of the trees in T _2k+1. Specifically, 10 trees T ₂,T ₃,⋯,T ₁₁ and two classes of trees T(1) and T(12) in T _2k+1 are introduced. It is shown in this paper that for each tree T ₁ ^′, T ₁ ^″ ∈ T(1) and T ₁₂ ^′, T ₁₂ ^″ ∈ T(12) and each i, j with 2 ≤ i < j <-11, α(T ₁ ^′) = α(T ₁ ^″) > α(T _i) > α(T _j) > α(T ₁₂ ^′) = α(T ₁₂ ^″). It is also shown that for each tree T with T ∈ T _2k+1 (T(1) ∪ {T ₂,_{T 3},⋯,T ₁₁} ∪ T(12)), α(T ₁₂ ^′) > α(T).

Keywords

Laplacian eigenvalue / Tree / Nearly perfect matching / Algebraic connectivity

References

[1] Cvetković D. M., Doob M., Sachs H.. Spectra of Graphs-Theory and Applications, 1979, Berlin: VEB Deutscher Verlag d. Wiss.

[2] Fiedler M.. Algebraic connectivity graphs. Czech. Math. J., 1973, 23(98): 298-305

[3] Fiedler M.. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J., 1975, 25(100): 619-633

[4] Fiedler M.. Eigenvectors of acyclic matrices. Czech. Math. J., 1975, 25(100): 607-618

[5] Kikland S., Neumann M., Shader B. L.. Characteristic vertices of weighted trees via Perron values. Linear Multilinear Algebra, 1996, 40: 311-325

[6] Bapat R. B., Pati S.. Algebraic connectivity and the characteristic set of a graph. Linear Multilinear Algebra, 1998, 45: 247-273

[7] Merris R.. Characteristic vertices of trees. Linear Multilinear Algebra, 1987, 22: 115-131

[8] Grone R., Merris R.. Ordering trees by algebraic connectivity. Graphs Combi., 1990, 6: 229-237

[9] Yin S.-H., Shu J.-L., Wu Y.-R.. Graft and algebraic connectivity of trees (in Chinese). J. East China Norm. Univ. (Natur. Sci.), 2005, 2: 6-15

[10] Grone R., Merris R.. Algebraic connectivity of trees. Czech. Math. J., 1987, 37(112): 660-670