Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. It is known that the algebraic connectivity of a n-vertex path P_n is 2(1-cos(\pi/n)). Now, my question is what is the algebraic connectivity of a tree which is formed by connecting an isolated vertex to the second vertex of a path P_{n-1} ? Or, can you find its approximate value ?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Firstly, your tree is just a Coxeter/Dynkin diagram of type $D$, so you may want to search MathSciNet with this in mind as your question might have been answered exactly at some point.

If you are happy enough with some bounds, it's easy to obtain $$\frac{4}{n(n-2)}\leq \lambda_2(P)\leq \frac{12(n+2)}{n(n^2-1)},$$ so that $\lambda_2(P)=\Theta\left(\frac{1}{n(n-1)}\right).$ (See Bojan Mohar's algebraic connectivity survey, Equations 6.10 and 7.1.) Perhaps a more in-depth reading of that paper would get you a better answer.

share|improve this answer
    
Thanks for your answer. Actually, it helps. Now, I wonder that can we enhance the lower bound to 10/n(n−2)≤λ_2. –  Tylar Liu Jul 13 '11 at 16:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.