Name
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 ) ⩽ ⌈2 n /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 ) ⩽ 2 n /5, providing a new upper bound for cubic graphs. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0012-365X(98)00350-1 | Discrete Mathematics |
Keywords | Field | DocType |
independent domination number,regular graph,05c35,maximal independent set,satisfiability,cubic graph,upper bound,domination number | Random regular graph,Discrete mathematics,Strongly regular graph,Combinatorics,Bound graph,Graph power,Cubic graph,Regular graph,Distance-regular graph,Symmetric graph,Mathematics | Journal |
Volume | Issue | ISSN |
202 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
13 | 1.31 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Che Bor Lam | 1 | 164 | 17.66 |
| Wai Chee Shiu | 2 | 167 | 28.28 |
| Liang Sun | 3 | 18 | 3.19 |