✦ LIBER ✦

Set domination in graphs

✍ Scribed by E. Sampathkumar; L. Pushpa Latha

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 γ~s~(G) of G is the minimum cardinality of a sd‐set. In this paper we develop properties of this new parameter and relate it to some other known domination parameters.

📜 SIMILAR VOLUMES

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

Signed Domination in Regular Graphs and

Signed Domination in Regular Graphs and Set-Systems

✍ Zoltán Füredi; Dhruv Mubayi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Suppose G is a graph on n vertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of G with colors, +1 and &1, such that all closed neighborhoods contain more 1's than &1's, and all together the number of 1's does not exceed the numb

Independent perfect domination sets in C

Independent perfect domination sets in Cayley graphs

✍ Jaeun Lee 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube __Q~n~__ has an independent perfect domination set if and only if __Q~n~__ i

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

Total domination in graphs

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

Domination-balanced graphs

✍ Charles Payan; Nguyen Huy Xuong 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## 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 part