On the ratio of the domination number and the independent domination number in graphs

被引:7
作者
Furuya, Michitaka [1 ]
Ozeki, Kenta [2 ,3 ]
Sasaki, Akinari [1 ]
机构
[1] Tokyo Univ Sci, Dept Math Informat Sci, Shinjuku Ku, Tokyo 1628601, Japan
[2] Res Org Informat & Syst, Natl Inst Informat, Chiyoda Ku, Tokyo 1018430, Japan
[3] JST, ERATO, Kawarabayashi Large Graph Project, Kawaguchi, Saitama, Japan
关键词
Domination number; Independent domination number; Maximum degree;
D O I
10.1016/j.dam.2014.06.005
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We let gamma(G) and i(G) denote the domination number and the independent domination number of G, respectively. Recently, Rad and Volkmann conjectured that i(G)/gamma(G) <= Delta(G)/2 for every graph G, where Delta(G) is the maximum degree of G. In this note, we construct counterexamples of the conjecture for Delta(G) >= 6 and give a sharp upper bound of the ratio i(G)/gamma(G) by using the maximum degree of G. (C) 2014 Elsevier BM. All rights reserved.
引用
收藏
页码:157 / 159
页数:3
相关论文
共 6 条
[1]  
DIESTEL R., 2012, Grad. Texts in Math., V173
[2]   Independent domination in graphs: A survey and recent results [J].
Goddard, Wayne ;
Henning, Michael A. .
DISCRETE MATHEMATICS, 2013, 313 (07) :839-854
[3]   On the Independent Domination Number of Regular Graphs [J].
Goddard, Wayne ;
Henning, Michael A. ;
Lyle, Jeremy ;
Southey, Justin .
ANNALS OF COMBINATORICS, 2012, 16 (04) :719-732
[4]  
Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]
[5]   A note on the independent domination number in graphs [J].
Rad, Nader Jafari ;
Volkmann, Lutz .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) :3087-3089
[6]   Domination versus independent domination in cubic graphs [J].
Southey, Justin ;
Henning, Michael A. .
DISCRETE MATHEMATICS, 2013, 313 (11) :1212-1220