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

• Published in: Linear algebra and its applications 2008-02, Vol.428 (4), p.855-864
• Main Authors: Patra, K.L., Lal, A.K.
• Format: Article
• Language: English
• Subjects: Algebra; Algebraic connectivity; Combinatorics; Combinatorics. Ordered structures; Exact sciences and technology; Graph theory; Laplacian matrix; Linear and multilinear algebra, matrix theory; Mathematics; Sciences and techniques of general use; Tree
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2007.08.018

Let G = ( V , E ) be a tree on n ⩾ 2 vertices and let v ∈ V . Let L ( G ) be the Laplacian matrix of G and μ ( G ) be its algebraic connectivity. Let G k , l , be the graph obtained from G by attaching two new paths P : vv 1 v 2 … v k and Q : vu 1 u 2 … u l of length k and l , respectively, at v . We prove that if l ⩾ k ⩾ 1 then μ ( G k - 1 , l + 1 ) ⩽ μ ( G k , l ) . Let ( v 1 , v 2 ) be an edge of G . Let G ∼ be the tree obtained from G by deleting the edge ( v 1 , v 2 ) and identifying the vertices v 1 and v 2 . Then we prove that μ ( G ) ⩽ μ ( G ∼ ) . As a corollary to the above results, we obtain the celebrated 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.