TY - JOUR

T1 - On independent domination number of regular graphs

AU - Che Bor Lam, Peter

AU - SHIU, Wai Chee

AU - Sun, Liang

N1 - Funding Information:
* Corresponding author: E-mail: [email protected], ’ Partially supported by Faculty Research Grant, Hong Kong Baptist * Research was done while visiting Hong Kong Baptist University.

PY - 1999/5

Y1 - 1999/5

N2 - Let G be a simple graph. The independent domination number i(G) is the minimum cardinality among all maximal independent sets of G. Haviland (1995) conjectured that any connected regular graph G of order n and degree δ ≤ n/2 satisfies i(G) ≤ [2n/3δ]δ/2. In this paper, we will settle the conjecture of Haviland in the negative by constructing counterexamples. Therefore a larger upper bound is expected. We will also show that a connected cubic graph G of order n ≥ 8 satisfies i(G) ≤ 2n/5, providing a new upper bound for cubic graphs.

AB - Let G be a simple graph. The independent domination number i(G) is the minimum cardinality among all maximal independent sets of G. Haviland (1995) conjectured that any connected regular graph G of order n and degree δ ≤ n/2 satisfies i(G) ≤ [2n/3δ]δ/2. In this paper, we will settle the conjecture of Haviland in the negative by constructing counterexamples. Therefore a larger upper bound is expected. We will also show that a connected cubic graph G of order n ≥ 8 satisfies i(G) ≤ 2n/5, providing a new upper bound for cubic graphs.

KW - Independent domination number

KW - Regular graph

UR - http://www.scopus.com/inward/record.url?scp=0042707122&partnerID=8YFLogxK

U2 - 10.1016/s0012-365x(98)00350-1

DO - 10.1016/s0012-365x(98)00350-1

M3 - Journal article

AN - SCOPUS:0042707122

SN - 0012-365X

VL - 202

SP - 135

EP - 144

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -