✦ LIBER ✦

Domination-balanced graphs

✍ Scribed by Charles Payan; Nguyen Huy Xuong

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 355 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060104

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A set D of vertices in a graph is said to be a dominating set if every vertex not in D is adjacent to some vertex in D. The domination number β(G) of a graph G is the size of a smallest dominating set. G is called domination balanced if its vertex set can be partitioned into β(G) subsets so that each subset is a smallest dominating set of the complement G of G. The purpose of this paper is to characterize these graphs.

📜 SIMILAR VOLUMES

Paired-domination in graphs

✍ Haynes, Teresa W.; Slater, Peter J. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 3 views

In a graph G Å (V, E) if we think of each vertex s as the possible location for a guard capable of protecting each vertex in its closed neighborhood N[s], then ''domination'' requires every vertex to be protected. Thus, S ʚ V (G) is a dominating set if ʜ s √ S N[s] Å V (G). For total domination, eac

Set domination in graphs

✍ E. Sampathkumar; L. Pushpa Latha 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ = (__V, E__) be a connected graph. A set __D__ ⊂ __V__ is a __set‐dominating set__ (sd‐set) if for every set __T__ ⊂ __V__ − __D__, there exists a nonempty set __S__ ⊂ __D__ such that the subgraph 〈__S__ ∪ __T__〉 induced by __S__ ∪ __T__ is connected. The set‐domination number

Vertex domination-critical graphs

✍ Jason Fulman; Denis Hanson; Gary Macgillivray 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 293 KB

Total domination in graphs

✍ E. J. Cockayne; R. M. Dawes; S. T. Hedetniemi 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB

Vertex domination-critical graphs

✍ Robert C. Brigham; Phyllis Z. Chinn; Ronald D. Dutton 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB

Domination critical graphs with higher i

Domination critical graphs with higher independent domination numbers

✍ Ao, S.; Cockayne, E.J.; MacGillivray, G.; Mynhardt, C.M. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB 👁 2 views

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.