Dominating set

From Wikipedia, the free encyclopedia

In graph theory, a dominating set for a graph G = (V, E) is a subset V′ of V such that every vertex not in V′ is joined to at least one member of V′ by some edge. The domination number γ(G) is the number of vertices in the smallest dominating set for G.

As Hedetniemi and Laskar (1990) note, the domination problem was studied from the 1950s onwards, but the rate of research on domination significantly increased in the mid-1970s. Their bibliography lists over 300 papers related to domination in graphs.

[edit] Related topics

The dominating set problem concerns testing whether γ(G) ≤ K for a given input K; it is NP-complete (Garey and Johnson 1979). Another NP-complete problem involving domination is the domatic number problem, in which one must partition the vertices of a graph into a given number of dominating sets; the maximum number of sets in any such partition is the domatic number of the graph.

Vizing's conjecture relates the domination number of a cartesian product of graphs to the domination number of its factors.

Dominating sets are closely related to independent sets: a maximal independent set in a graph is necessarily a minimal dominating set. However, dominating sets need not be independent, and there has been much work on connected dominating sets. If S is a connected dominating set, one can form a spanning tree of G in which S forms the set of non-leaf nodes of the tree; conversely, if T is any spanning tree in a graph with more than two vertices, the non-leaf nodes of T form a connected dominating set. Therefore, finding minimum connected dominating sets is equivalent to finding spanning trees with the maximum possible number of leaves.

A total dominating set is a set of vertices such that all vertices in the graph (including the vertices in the dominating set themselves) have a neighbor in the dominating set.

[edit] Example

Suppose that G is a cycle of eight vertices v_i, 0 ≤ i < 8, with v_i adjacent to v_{i - 1 (mod 8)} and to v_{i + 1 (mod 8)}. Then G can be dominated by three vertices; e.g., {v₀, v₃, v₆}. Each other vertex is adjacent to one of these three positions. That is, γ(G) = 3. However, the smallest total dominating set for G consists of four vertices, e.g. {v₀, v₁, v₄, v₅}. The smallest connected dominating set for G consists of six vertices, e.g. {v₀, v₁, v₂, v₃, v₄, v₅}. And the largest minimal dominating set for G has four vertices: {v₀, v₂, v₄, v₆}.

[edit] References

• Garey, M.; Johnson, D. (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0716710455.

• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998). Fundamentals of Domination in Graphs. Marcel Dekker. ISBN 0824700333.

• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998). Domination in Graphs: Advanced Topics. Marcel Dekker. ISBN 0824700341.

• Hedetniemi, S. T.; Laskar, R. C. (1990). "Bibliography on domination in graphs and some basic definitions of domination parameters". Discrete Mathematics 86 (1–3): 257–277. DOI:10.1016/0012-365X(90)90365-O.