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 条

[1]

Alon N., 1990, TRANSVERSAL NUMBERS, V6, P1

[2]

Arnautov V.I., 1974, Prikl. Mat. i Prog, V11, P3

[3]

Biro Cs., 2012, Bull. Inst. Combin. Appl, V64, P73

[4]

Blank M.M., 1973, PRIKL MAT PROGRAMMIR, P3

[5] Dominating sequences in graphs [J].

Bresar, Bostjan ;

Gologranc, Tanja ;

Milanic, Martin ;

Rall, Douglas F. ;

Rizzi, Romeo .

DISCRETE MATHEMATICS, 2014, 336 :22-36

[6] DOMINATION GAME AND AN IMAGINATION STRATEGY [J].

Bresar, Bostjan ;

Klavzar, Sandi ;

Rall, Douglas F. .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) :979-991

[7]

Bujtas Cs., 2013, P 8 JAPANESE HUNGARI, P73

[8]

Bujtas Cs, 2014, ARXIV14067372

[9]

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

[10]

CLARK WE, 1997, ELECTRON J COMB, V4, pR26

← 1 2 3 →