Improved Upper Bounds on the Domination Number of Graphs With Minimum Degree at Least Five

被引：15

作者：

Bujtas, Csilla ^{[1
]}

Klavzar, Sandi ^{[2
,3
,4
]}

机构：

[1] Univ Pannonia, Dept Comp Sci & Syst Technol, Veszprem, Hungary

[2] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia

[3] Univ Maribor, Fac Nat Sci & Math, SLO-2000 Maribor, Slovenia

[4] Inst Math Phys & Mech, Ljubljana, Slovenia

来源：

GRAPHS AND COMBINATORICS | 2016年 / 32卷 / 02期

关键词：

Domination number; Minimum degree; Greedy algorithm; CONNECTED CUBIC GRAPHS; GAME;

D O I：

10.1007/s00373-015-1585-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An algorithmic upper bound on the domination number of graphs in terms of the order n and the minimum degree is proved. It is demonstrated that the bound improves best previous bounds for any . In particular, for , Xing et al. (Graphs Comb. 22:127-143, 2006) proved that . This bound is improved to 0.3440 n. For , Clark et al. (Congr. Numer. 132:99-123, 1998) established , while Bir et al. (Bull. Inst. Comb. Appl. 64:73-83, 2012) recently improved it to . Here the bound is further improved to . For , the best earlier bound 0.3088n is improved to gamma < 0.2927n.

引用

页码：511 / 519

页数：9

共 24 条

[11]

Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]

[12]

Imrich Wilfried, 2008, Topics in graph theory: graphs and their cartesian product

[13] EXTREMAL PROBLEMS FOR GAME DOMINATION NUMBER [J].

Kinnersley, William B. ;

West, Douglas B. ;

Zamani, Reza .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (04) :2090-2107

[14] An upper bound on the domination number of n-vertex connected cubic graphs [J].

Kostochka, A. V. ;

Stodolsky, B. Y. .

DISCRETE MATHEMATICS, 2009, 309 (05) :1142-1162

[15] Domination number of cubic graphs with large girth [J].

Kral', Daniel ;

Skoda, Petr ;

Volec, Jan .

JOURNAL OF GRAPH THEORY, 2012, 69 (02) :131-142

[16] Domination in graphs of minimum degree at least two and large girth [J].

Loewenstein, Christian ;

Rautenbach, Dieter .

GRAPHS AND COMBINATORICS, 2008, 24 (01) :37-46

[17] Pairs of Disjoint Dominating Sets in Connected Cubic Graphs [J].

Loewenstein, Christian ;

Rautenbach, Dieter .

GRAPHS AND COMBINATORICS, 2012, 28 (03) :407-421

[18] DOMINATION IN GRAPHS WITH MINIMUM DEGREE-2 [J].

MCCUAIG, W ;

SHEPHERD, B .

JOURNAL OF GRAPH THEORY, 1989, 13 (06) :749-762

[19]

Ore O., 1962, C PUBLICATIONS

[20]

Payan C., 1975, Cahiers Centre Etudes Recherche Oper, V17, P307

← 1 2 3 →