An upper bound on the domination number of n-vertex connected cubic graphs

被引：16

作者：

Kostochka, A. V. ^{[1
,2
]}

Stodolsky, B. Y. ^{[1
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Russian Acad Sci, Inst Math, Novosibirsk 630090, Russia

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 05期

基金：

俄罗斯基础研究基金会;

关键词：

Cubic graphs; Domination; Connected graphs;

D O I：

10.1016/j.disc.2007.12.009

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1996, Reed proved that the domination number gamma(G) of every n-vertex graph G with minimum degree at least 3 is at most 3n/8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that gamma(G) <= 4n/11 for every n-vertex cubic connected graph G if n > 8. Note that Reed's conjecture that gamma(G) <= inverted right perpendicularn/3inverted left perpendicular for every connected cubic n-vertex graph G is not true. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：1142 / 1162

页数：21

共 10 条

[1]

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

[2]

Cropper M, 2005, AKCE INT J GRAPHS CO, V2, P137

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

Kawarabayashi, K ;

Plummer, MD ;

Saito, A .

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

[4]

KELMANS A, COUNTEREXAMPLE UNPUB

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

Kostochka, AV ;

Stodolsky, BY .

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

[6]

LOWENSTEIN C, DOMINATION GRA UNPUB

[7]

ORE O, 1962, AM MATH SOC C PUB, V3

[8]

Plummer M., COMMUNICATION

[9]

Reed B. A., 1996, Combin. Probab. Comput., V5, P277

[10]

Stodolsky B. Y., DOMINATION 2 C UNPUB

← 1 →