TOPICS
Search

Upper Domination Number

The upper domination number Gamma(G) of a graph G is the maximum size of a minimal dominating set of vertices in G.

The (lower) domination number may be similarly defined as the minimum size of a dominating set of vertices in G (Burger et al. 1997, Mynhardt and Roux 2020).

The lower irredundance number ir(G), lower domination number gamma(G), lower independence number i(G), upper independence number alpha(G), upper domination number Gamma(G), and upper irredundance number IR(G) satsify the chain of inequalities

ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)

(Burger et al. 1997).

See also

Dominating Set, Domination Number, Domination Polynomial

Explore with Wolfram|Alpha

References

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).Hedetniemi, S. T. and Laskar, R. C. "A. Bibliography on Dominating Sets in Graphs and Some Basic Definitions of Domination Parameters." Disc. Math. 86, 257-277, 1990.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.

Cite this as:

Weisstein, Eric W. "Upper Domination Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UpperDominationNumber.html

Subject classifications