Total Domination Number

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The total domination number 👁 gamma_t
of a graph is the size of a smallest total dominating set, where a total dominating set is a set of vertices of the graph such that all vertices (including those in the set itself) have a neighbor in the set. Total dominating numbers are defined only for graphs having no isolated vertex (plus the trivial case of the singleton graph 👁 K_1
). In other words, the total domination number is the size of a minimum total dominating set.

For example, in the Petersen graph illustrated above, 👁 gamma(P)=3
since the set 👁 S={1,2,9}
is a minimum dominating set (left figure), while 👁 gamma_t(P)=4
since 👁 S^t={4,8,9,10}
is a minimum total dominating set (right figure).

For any simple graph 👁 G
with no isolated points, the total domination number 👁 gamma_t
and ordinary domination number 👁 gamma
satisfy

(Henning and Yeo 2013, p. 17). In addition, if 👁 G
is a bipartite graph, then

(Azarija et al. 2017), where 👁 square
denotes the graph Cartesian product.

For a connected graph 👁 G
with vertex count 👁 n>=3
,

(Cockayne et al. 1980; Henning and Yeo 2013, p. 11).

See also

Dominating Set, Domination Number, Minimum Total Dominating Set, Total Dominating Set

Explore with Wolfram|Alpha

References

Azarija, J.; Henning, M. A.; and Klavžar, S. "(Total) Domination in Prisms." Electron. J. Combin. 24, No. 1, paper 1.19, 2017. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p19.Cockayne, E. J., Dawes, R. M., and Hedetniemi, S. T. "Total Domination in Graphs." Networks 10, 211-219, 1980.Henning, M. A. and Yeo, A. Total Domination in Graphs. New York: Springer, 2013.

Referenced on Wolfram|Alpha

Total Domination Number

Cite this as:

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

Subject classifications