The ordering of trees and connected graphs by algebraic connectivity

By J. Shao, Ji-Ming Guo, H. Shan. 2008

46 citations recorded by the source corpus.

Abstract 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 P n , Q n , Q n ′ , W n , W n ′ and W n ″ , with α ( P n ) α ( Q n ) = α ( Q n ′ ) α ( W n ) = α ( W n ′ ) = α ( W n ″ ) α ( G ) , where G is any connected graph of order n other than P n , Q n , Q n ′ , W n , W n ′ and W n ″ .

Subfields: Geometry and Topology, Inorganic Chemistry, Organic Chemistry

View Paper: https://www.semanticscholar.org/paper/2095fcd1a263f8ff3b7cb292cbcfed43d512c742