Domination number of cubic graphs with large girth

被引：7

作者：

Kral', Daniel ^{[1
,2
]}

Skoda, Petr ^{[3
]}

Volec, Jan ^{[1
]}

机构：

[1] Charles Univ Prague, Dept Appl Math, Fac Math & Phys, CR-11800 Prague, Czech Republic

[2] Charles Univ Prague, Inst Theoret Comp Sci, Fac Math & Phys, CR-11800 Prague, Czech Republic

[3] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

来源：

JOURNAL OF GRAPH THEORY | 2012年 / 69卷 / 02期

关键词：

domination; dominating number; cubic graphs; probabilistic method;

D O I：

10.1002/jgt.20568

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+ O(n/g)<3n/10 + O(n/g) which improves a previous bound of 0.321216n+ O(n/g) by Rautenbach and Reed. (C) 2011 Wiley Periodicals, Inc. J Graph Theory 69:131-142, 2012

引用

页码：131 / 142

页数：12

共 10 条

[1] Minimum independent dominating sets of random cubic graphs [J].

Duckworth, W ;

Wormald, NC .

RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (02) :147-161

[2] Domination in a graph with a 2-factor [J].

Kawarabayashi, K ;

Plummer, MD ;

Saito, A .

JOURNAL OF GRAPH THEORY, 2006, 52 (01) :1-6

[3]

Kelmans A., ARXIVMATHCO0607512

[4] 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

[5] On domination in connected cubic graphs [J].

Kostochka, AV ;

Stodolsky, BY .

DISCRETE MATHEMATICS, 2005, 304 (1-3) :45-50

[6] 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

[7] THE DOMINATING NUMBER OF A RANDOM CUBIC GRAPH [J].

MOLLOY, M ;

REED, B .

RANDOM STRUCTURES & ALGORITHMS, 1995, 7 (03) :209-221

[8]

Rautenbach D, 2008, LECT NOTES COMPUT SC, V4535, P186

[9]

REED B, 1996, COMBIN PROB COMPUT, V5, P267

[10]

Wormald N. C., 2009, COMMUNICATION

← 1 →