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 ?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Thanks for your answer. Actually, it helps. Now, I wonder that can we enhance the lower bound to 10/n(n−2)≤λ_2. $\endgroup$ Commented Jul 13, 2011 at 16:58