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 ?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
|
|
|
|
|
3
|
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. |
|||
|
