The ordering of trees and connected graphs by algebraic connectivity

✍ Scribed by Jia-Yu Shao; Ji-Ming Guo; Hai-Ying Shan

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 235 KB
• Volume: 428
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2007.08.031

✦ Synopsis

In this paper, we first determine that the first four trees of order n 9 with the smallest algebraic connectivity are P n , Q n , W n and Z n with α(P n ) < α(Q n ) < α(W n ) < α(Z n ) < α(T ), where T is any tree of order n other than P n , Q n , W n , and Z n . Then we consider the effect on the Laplacian eigenvalues of connected graphs by suitably adding edges. By using these results and methods, we finally determine that the first six connected graphs of order n 9 with the smallest algebraic connectivity are

, where G is any connected graph of order n other than P n , Q n , Q n , W n , W n and W n .