Domination in graphs of minimum degree at least two and large girth

被引:17
作者
Loewenstein, Christian [1 ]
Rautenbach, Dieter [1 ]
机构
[1] Tech Univ Ilmenau, Inst Math, D-98684 Ilmenau, Germany
关键词
domination number; minimum degree; girth; cubic graph;
D O I
10.1007/s00373-007-0770-8
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that for graphs of order n, minimum degree delta >= 2 and girth g >= 5 the graphs of order n and girth g >= 5 the domination number. satisfies gamma <= (44/135 + 82/135g) n which improves recent results due to Kostochka and Stodolsky ( An upper bound on the domination number of n-vertex connected cubic graphs, manuscript ( 2005)) and Kawarabayashi, Plummer and Saito ( Domination in a graph with a 2-factor, J.Graph Theory 52 ( 2006), 1-6) for large enough girth. Furthermore, it confirms a conjecture due to Reed about connected cubic graphs ( Paths, stars and the number three, Combin. Prob. Comput. 5 ( 1996), 267 - 276) for girth at least 83.
引用
收藏
页码:37 / 46
页数:10
相关论文
共 15 条
[1]  
[Anonymous], PRIKL MATH PROGRAMMI
[2]  
[Anonymous], DISCRETE MATH
[3]   BOUNDS ON THE DOMINATION NUMBER OF A GRAPH [J].
BRIGHAM, RC ;
DUTTON, RD .
QUARTERLY JOURNAL OF MATHEMATICS, 1990, 41 (163) :269-275
[4]   On colouring the nodes of a network [J].
Brooks, RL .
PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197
[5]  
Haynes T.W., 1998, FUNDAMENTALS DOMINAT
[6]   Domination in a graph with a 2-factor [J].
Kawarabayashi, K ;
Plummer, MD ;
Saito, A .
JOURNAL OF GRAPH THEORY, 2006, 52 (01) :1-6
[7]   On domination in connected cubic graphs [J].
Kostochka, AV ;
Stodolsky, BY .
DISCRETE MATHEMATICS, 2005, 304 (1-3) :45-50
[8]  
KOSTOCHKA AV, 2005, UNPUB UPPER BOUND DO
[9]   DOMINATION IN GRAPHS WITH MINIMUM DEGREE-2 [J].
MCCUAIG, W ;
SHEPHERD, B .
JOURNAL OF GRAPH THEORY, 1989, 13 (06) :749-762
[10]  
Ore Oystein., 1962, Theory of Graphs