On independent domination number of regular graphs

Peter Che Bor Lam; Wai Chee SHIU; Liang Sun

doi:10.1016/s0012-365x(98)00350-1

On independent domination number of regular graphs

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

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

35 Citations (Scopus)

2 Downloads (Pure)

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	https://doi.org/10.1016/s0012-365x(98)00350-1
Publication status	Published - May 1999

Scopus Subject Areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

User-Defined Keywords

Independent domination number
Regular graph

Access to Document

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

Full Text

Cite this

@article{67433fd981514cc2873e5a9add22ff87,

title = "On independent domination number of regular graphs",

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.",

keywords = "Independent domination number, Regular graph",

author = "{Che Bor Lam}, Peter and SHIU, {Wai Chee} and Liang Sun",

note = "Funding Information: * Corresponding author: E-mail: cblam@math.hkbu.edu.hk, {\textquoteright} Partially supported by Faculty Research Grant, Hong Kong Baptist * Research was done while visiting Hong Kong Baptist University.",

year = "1999",

month = may,

doi = "10.1016/s0012-365x(98)00350-1",

language = "English",

volume = "202",

pages = "135--144",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

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: cblam@math.hkbu.edu.hk, ’ 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 -

On independent domination number of regular graphs

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this