On independent domination number of regular graphs

Peter Che Bor Lam*, Wai Chee SHIU, Liang Sun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)

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 languageEnglish
Pages (from-to)135-144
Number of pages10
JournalDiscrete Mathematics
Volume202
Issue number1-3
DOIs
Publication statusPublished - May 1999

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Independent domination number
  • Regular graph

Fingerprint

Dive into the research topics of 'On independent domination number of regular graphs'. Together they form a unique fingerprint.

Cite this