TY - JOUR
T1 - Triangle-free graphs with large independent domination number
AU - Shiu, Wai Chee
AU - Chen, Xue gang
AU - Chan, Wai Hong
N1 - Funding Information:
This work is partially supported by GRF of Research Grant Council of Hong Kong, FRG of Hong Kong Baptist University and Doctoral Research Grant of North China Electric Power University (200722026).
PY - 2010/2
Y1 - 2010/2
N2 - Let G be a simple graph of order n and minimum degree δ. The independent domination number i (G) is defined as the minimum cardinality of an independent dominating set of G. We prove the following conjecture due to Haviland [J. Haviland, Independent domination in triangle-free graphs, Discrete Mathematics 308 (2008), 3545-3550]: If G is a triangle-free graph of order n and minimum degree δ, then i (G) ≤ n - 2 δ for n / 4 ≤ δ ≤ n / 3, while i (G) ≤ δ for n / 3 < δ ≤ 2 n / 5. Moreover, the extremal graphs achieving these upper bounds are also characterized.
AB - Let G be a simple graph of order n and minimum degree δ. The independent domination number i (G) is defined as the minimum cardinality of an independent dominating set of G. We prove the following conjecture due to Haviland [J. Haviland, Independent domination in triangle-free graphs, Discrete Mathematics 308 (2008), 3545-3550]: If G is a triangle-free graph of order n and minimum degree δ, then i (G) ≤ n - 2 δ for n / 4 ≤ δ ≤ n / 3, while i (G) ≤ δ for n / 3 < δ ≤ 2 n / 5. Moreover, the extremal graphs achieving these upper bounds are also characterized.
KW - Independent domination number
KW - Triangle-free graphs
UR - http://www.scopus.com/inward/record.url?scp=77950521304&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2010.02.004
DO - 10.1016/j.disopt.2010.02.004
M3 - Journal article
AN - SCOPUS:77950521304
SN - 1572-5286
VL - 7
SP - 86
EP - 92
JO - Discrete Optimization
JF - Discrete Optimization
IS - 1-2
ER -