A sharp upper bound on algebraic connectivity using domination number

被引：7

作者：

Aouchiche, M. ^{[1
,2
]}

Hansen, P. ^{[1
,2
,3
]}

Stevanovic, D. ^{[4
,5
]}

机构：

[1] Ecole Hautes Etud Commerciales, Gerad, Montreal, PQ, Canada

[2] HEC Montreal, Montreal, PQ, Canada

[3] Ecole Polytech, LIX, Palaiseau, France

[4] Univ Nis, PMF, Nish, Serbia

[5] Univ Primorska, FAMNIT, Koper, Slovenia

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2010年 / 432卷 / 11期

关键词：

Algebraic connectivity; Laplacian; Domination number; Extremal graph; VARIABLE NEIGHBORHOOD SEARCH; EXTREMAL GRAPHS;

D O I：

10.1016/j.laa.2009.12.031

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2010 Elsevier Inc. All rights reserved.

引用

页码：2879 / 2893

页数：15

共 18 条

[1]

Aouchiche M, 2006, NONCON OPTIM ITS APP, V84, P281

[2]

AOUCHICHE M, 2005, ELECT NOTES DISCRETE, V22, P515, DOI DOI 10.1016/J.ENDM.2005.06.090

[3]

Aouchiche M, 2007, MATCH-COMMUN MATH CO, V58, P365

[4] Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures [J].

Caporossi, G ;

Hansen, P .

DISCRETE MATHEMATICS, 2004, 276 (1-3) :81-94

[5] Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system [J].

Caporossi, G ;

Hansen, P .

DISCRETE MATHEMATICS, 2000, 212 (1-2) :29-44

[6]

Clark W.E., 1998, Congr. Numer, V132, P99

[7]

CLARK WE, 1997, ELECT J COMBIN, V4

[8]

Cvetkovi DM., 1980, Spectra of Graphs: Theory and Applications

[9] Old and new results on algebraic connectivity of graphs [J].

de Abreu, Nair Maria Maia .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :53-73

[10]

FIEDLER M, 1973, CZECH MATH J, V23, P298

← 1 2 →