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


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

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

(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

Explore with Wolfram|Alpha


Azarija, J.; Henning, M. A.; and Klavžar, S. "(Total) Domination in Prisms." Electron. J. Combin. 24, No. 1, paper 1.19, 2017., 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.

Subject classifications