G-2009-22
A Sharp Upper Bound on Algebraic Connectivity Using Domination Number
, et référence BibTeX
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.
Paru en mai 2009 , 20 pages
Ce cahier a été révisé en décembre 2009
Axe de recherche
Applications de recherche
Publication
jan. 2010
A sharp upper bound on algebraic connectivity using domination number
, et
Linear Algebra and its Applications, 432(11), 2879–2893, 2010
référence BibTeX