Discrete Mathematics & Theoretical Computer Science, Vol 9, No 1 (2007)

Font Size:  Small  Medium  Large

On the kth Eigenvalues of Trees with Perfect Matchings

Wai Chee Shiu, An Chang

Abstract


Let Τ+2p be the set of all trees on 2p (p≥ 1) vertices with perfect matchings. In this paper, we prove that for any tree T in Τ+2p, its k-th largest eigenvalue λk(T) satisfies λk(T)≤ 1 / 2 ( √{⌈p / k⌉-1}+ √{⌈p / k⌉+3}) (k=1,2,..,p) and show that this upper bound is the best possible when k=1. The set of trees obtained from a tree on p vertices by joining a pendent vertex to each vertex of the tree, respectively, is denoted by Τ*2p. We also prove that for any tree T in Τ*2p, its k-th largest eigenvalue λk(T) satisfies

λk(T)≤ 1 / 2 (√{ ⌊p / k ⌋-1}+√{ ⌊p / k ⌋+3})

(k=1,2,&elip;,p) and show that this upper bound is the best possible when k=1 or p¬≡ 0 mod k. We further give the following inequality

{λ}k* (2p)> 1 / 2(√{t-1-√{(k-1)/(t-k)}}+ √{t+3-√{(k-1)/(t-k)}}) t= ⌊p / k ⌋,

where {λ}k^* (2p) is the maximum value of the k-th largest eigenvalue of the trees in Τ*2p. By this inequality, it is easy to see that the above upper bound on λk(T) for T∈ Τ*2p turns out to be asymptotically good when p≡ 0mod k.

Full Text: PDF PostScript