A sharp upper bound on algebraic connectivity using domination number

✍ Scribed by M. Aouchiche; P. Hansen; D. Stevanović

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 760 KB
• Volume: 432
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2009.12.031

✦ Synopsis

Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the domination number. In this paper, we prove a sharp upper bound on the algebraic connectivity of a connected graph in terms of the domination number and characterize the associated extremal graphs.