TOPICS
Search

Total Domination Number


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).

TotalDominatingSet

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

 gamma<=gamma_t<=2gamma
(1)

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

 gamma_t(G square K_2)=2gamma(G),
(2)

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

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

 gamma_t(G)<=2/3n
(3)

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


See also

Dominating Set, Domination Number

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.

Cite this as:

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

Subject classifications