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 - Article

AN - SCOPUS:77950521304

VL - 7

SP - 86

EP - 92

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

IS - 1-2

ER -