TOPICS
Search

Total Domination Polynomial


The total domination polynomial T_G(x) of a graph G counts its total dominating sets by size (Latheeshkumar and Anil Kumar 2017). If t_G(k) counts the total dominating sets of size k, then

 T_G(x)=sum_(k=0)^(|V(G)|)t_G(k)x^k.

When T_G(x) is nonzero, its least exponent is the total domination number of G. A graph with an isolated vertex has T_G(x)=0.

For the complete graph K_n with n>=2, every subset of at least two vertices is a total dominating set, so

 T_(K_n)(x)=(1+x)^n-1-nx.

See also

Domination Polynomial, Total Dominating Set, Total Domination Number

Explore with Wolfram|Alpha

References

Latheeshkumar, A. R. and Anil Kumar, V. "TD-Polynomials of Paths and Cycles--A New Approach." Global J. Pure Appl. Math. 13, 7315-7319, 2017. https://www.ripublication.com/gjpam17/gjpamv13n10_26.pdf.

Cite this as:

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

Subject classifications