most recent 30 from http://mathoverflow.net 2013-05-21T09:13:27Z http://mathoverflow.net/feeds/question/70128 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70128/a-computation-problem-of-algebraic-connectivity-of-a-tree Tylar Liu 2011-07-12T14:40:41Z 2011-07-12T17:26:53Z

<p>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 ? </p>

http://mathoverflow.net/questions/70128/a-computation-problem-of-algebraic-connectivity-of-a-tree/70153#70153 Casteels 2011-07-12T17:26:53Z 2011-07-12T17:26:53Z

<p>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. </p> <p>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.</p>