lower domination number

The (lower) domination number γ(G) of a graph G is the minimum size of a dominating set of vertices in G, i.e., the size of a minimum dominating set. This is equivalent to the smallest size of a minimal dominating set since every minimum dominating set is also minimal. The domination number is also equal to smallest exponent in a domination polynomial. For example, in the Petersen graph P illustrated above, the set S = {1, 2, 9} is a minimum dominating set, so γ(P) = 3. The upper domination number Γ(G) may be similarly defined as the maximum size of a minimal dominating set of vertices in G (Burger et al. 1997, Mynhardt and Roux 2020).

connected domination number | domatic number | domatic partition | dominance | dominating set | domination polynomial | minimum dominating set | total domination number | upper domination number | Vizing conjecture