The six classes of trees with the largest algebraic connectivity (Q2476262): Difference between revisions

The algebraic connectivity of a graph \(G\), \(\alpha(G)\), is the \((n{-}1)\)-st eigenvalue of its Laplacian matrix. In the paper the authors introduce six classes \(C_1\dots C_6\) of trees of order \(n\), and prove that if \(T\) is a tree of order \(n\geq 15\), then \(\alpha(T)\geq 2-\sqrt{3}\) if and only if \(T\in\bigcup_{i=1}^6C_i\), where the equality holds if and only if \(T\) is a tree in class \(C_6\). Further, a complete characterization of the equality case of a well-known relation between the algebraic connectivity of a tree \(T\) and the Peron value of the bottleneck matrix of a Peron branch is given.