Authors: Aouchiche, Mustapha
Hansen, Pierre
Stevanović, Dragan 
Title: A sharp upper bound on algebraic connectivity using domination number
Journal: Linear Algebra and Its Applications
Volume: 432
Issue: 11
First page: 2879
Last page: 2893
Issue Date: 1-Jun-2010
Rank: M22
ISSN: 0024-3795
DOI: 10.1016/j.laa.2009.12.031
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.
Keywords: Algebraic connectivity | Domination number | Extremal graph | Laplacian
Publisher: Elsevier

Show full item record


checked on Feb 8, 2023

Page view(s)

checked on Feb 8, 2023

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.