✦ LIBER ✦

Domination critical graphs with higher independent domination numbers

✍ Scribed by Ao, S.; Cockayne, E.J.; MacGillivray, G.; Mynhardt, C.M.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 348 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199605)22:1<9::aid-jgt2>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

We show that for each k L 4 there exists a connected k-domination critical graph with independent domination number exceeding k, thus disproving a conjecture of Sumner and Blitch ( J Cornbinatorial Theory B 34 (19831, 65-76) in all cases except k = 3.

📜 SIMILAR VOLUMES

Independence and hamiltonicity in 3-domi

Independence and hamiltonicity in 3-domination-critical graphs

✍ Favaron, Odile; Tian, Feng; Zhang, Lei 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisf

Graphs with large total domination numbe

Graphs with large total domination number

✍ Michael A. Henning 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

Total domination in graphs with minimum

Total domination in graphs with minimum degree three

✍ Favaron, Odile; Henning, Michael A.; Mynhart, Christina M.; Puech, Jo�l 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 1 views

A set S of vertices of a graph G is a total dominating set, if every vertex of V (G) is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at leas

k-Bounded classes of dominant-independen

k-Bounded classes of dominant-independent perfect graphs

✍ Zverovich, Igor E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 1 views

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a f

Bounds related to domination in graphs w

✍ Sanchis, Laura A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

A dominating set for a graph G = (V, E) is a subset of vertices V ⊆ V such that for all v ∈ V -V there exists some u ∈ V for which {v, u} ∈ E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q e

Dominating sets with small clique coveri

Dominating sets with small clique covering number

✍ Penrice, Stephen G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 1 views

Motivated by earlier work on dominating cliques, we show that if a graph G is connected and contains no induced subgraph isomorphic to P 6 or H t (the graph obtained by subdividing each edge of K 1,t , t ≥ 3, by exactly one vertex), then G has a dominating set which induces a connected graph with cl