Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 135-144 |
Number of pages | 10 |
Journal | Discrete Mathematics |
Volume | 202 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - May 1999 |
Scopus Subject Areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
User-Defined Keywords
- Independent domination number
- Regular graph