Article ID Journal Published Year Pages File Type
4602725 Linear Algebra and its Applications 2008 18 Pages PDF
Abstract

In this paper, we first determine that the first four trees of order n⩾9 with the smallest algebraic connectivity are Pn,Qn,Wn and Zn with α(Pn)<α(Qn)<α(Wn)<α(Zn)<α(T), where T is any tree of order n other than Pn, Qn, Wn, and Zn. 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 and , with , where G is any connected graph of order n other than Pn, Qn, , Wn, and .

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory