The effect on the algebraic connectivity of a tree by grafting or collapsing of edges (Q2469512)

In this paper the authors analyze the effect on the algebraic connectivity of a tree by grafting or collapsing of edges. Let \(G\) be a connected graph on \(n\) vertices with \(n \geq 2\) and \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_{n-1} > \lambda_n=0\) the eigenvalues of the Laplacian matrix \(L\) of \(G\). The second smallest eigenvalue of \(L\) is called the algebraic connectivity of \(G\) and it is denoted by \(\mu(G)\). Let \(v\) be a vertex of \(G\) and \(G_{k,l}\) the graph obtained from \(G\) by attaching two new paths \(P: vv_1v_2 \ldots v_k\) and \(Q:vu_1u_2 \ldots u_l\) of length \(k\) and \(l\), respectively, at \(v\), where \(u_1,u_2,\ldots,u_l\) and \(v_1,v_2,\ldots,v_k\) are distinct new vertices. On the other hand, let \((u,v)\) be an edge of \(G\) not lying on a cycle and \(\tilde{G}\) the graph obtained from \(G\) by deleting the edge \((u,v)\) and identifying \(u\) and \(v\). The authors show that if \(G\) is a tree and \(l \geq k \geq 1\) then \(\mu(G_{k-1,l+1})\leq \mu(G_{k,l})\). They also prove that \(\mu(G) \leq \mu(\tilde{G})\). As a corollary to these results, the authors obtain the theorem on algebraic connectivity which states that among all trees on \(n\) vertices, the path has the smallest and the star has the largest algebraic connectivity.