On independent domination number of regular graphs

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 delta less than or equal to n/2 satisfies i(G) less than or equal to inverted right perpendicular 2n/3 delta inverted left perpendicular delta/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 greater than or equal to 8 satisfies i(G) less than or equal to 2n/5, providing a new upper bound for cubic graphs. (C) 1999 Elsevier Science B.V. All rights reserved.