dominant set

For a graph G and a subset S of the vertex set V(G), denote by N_G[S] the set of vertices in G which are in S or adjacent to a vertex in S. If N_G[S] = V(G), then S is said to be a dominating set (of vertices in G). A dominating set of smallest size is called a minimum dominating set and its size is known as the domination number. A dominating set that is not a proper subset of any other dominating set is called a minimal dominating set. For example, in the Petersen graph illustrated above, the set S = {1, 2, 9} is a dominating set (and, in fact, a minimum dominating set). The domination polynomial encodes the numbers of dominating sets of various sizes.

connected domination number | domatic number | domatic partition | dominance | domination number | domination polynomial | minimal dominating set | minimum dominating set | total dominating set