Domination in a graph with a 2-factor

被引：12

作者：

Kawarabayashi, K

Plummer, MD

Saito, A

机构：

[1] Tohoku Univ, Grad Sch Informat Sci, Aoba Ku, Sendai, Miyagi 9808579, Japan

[2] Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA

[3] Nihon Univ, Dept Comp Sci, Setagaya Ku, Tokyo 1568550, Japan

来源：

JOURNAL OF GRAPH THEORY | 2006年 / 52卷 / 01期

关键词：

dominating set; domination number; 2-factor; girth; minimum degree;

D O I：

10.1002/jgt.20142

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let gamma(G) be the domination number of a graph G. Reed (6) proved that every graph G of minimum degree at least three satisfies gamma(G) <= (3/8)vertical bar G vertical bar, and conjectured that a better upper bound can be obtained for cubic graphs. In this paper, we prove that a 2-edge-connected cubic graph G of girth at least 3k satisfies gamma(G) <= ((3k + 2))/(9k + 3)vertical bar G vertical bar. For k >= 3, this gives gamma(G) <= (11/30)vertical bar G vertical bar, which is better than Reed's bound. In order to obtain this bound, we actually prove a more general theorem for graphs with a 2-factor. (c) 2006 Wiley Periodicals, Inc.

引用

页码：1 / 6

页数：6