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 -