TOPICS
Search

Domination Polynomial


Let d_G(k) be the number of dominating sets of size k in a graph G, then the domination polynomial D_G(x) of G in the variable x is defined as

 D_G(x)=sum_(k=gamma(G))^(|V(G)|)d_G(k)x^k,

where gamma(G) is the (lower) domination number of G (Kotek et al. 2012, Alikhani and Peng 2014).

D_G(x) is multiplicative over connected components (Alikhani and Peng 2014).

Nonisomorphic graphs may have the same domination polynomial. Graphs are said to be dominating equivalent if they have equal domination polynomials, and a graph that does not share a domination polynomial with any other nonisomorphic graph is said to be dominating unique (Akbari et al. 2010).

A root of the domination polynomial is called a domination root (Akbari et al. 2010).

Finding a minimum dominating set, and therefore also a domination polynomial, of a general graph is NP-complete, which can be shown by reduction from the vertex cover problem (Garey and Johnson 1983, Mertens 2024). This means that no polynomial-time algorithm exists to compute the domination polynomial (or even the domination number). The fastest known algorithm to find a minimum dominating set for a general graph with vertex count |G| has time complexity O(1.4969|G|) (van Rooij and Bodlaender 2011, Mertens 2024).

Precomputed domination polynomials for many named graphs in terms of a variable x and in the Wolfram Language as GraphData[graph, "DominationPolynomial"][x].

The following table summarizes closed forms for the domination polynomials of some common classes of graphs (cf. Alikhani and Peng 2014).

The following table summarizes the recurrence relations for domination polynomials for some simple classes of graphs.


See also

Domatic Number, Domatic Partition, Dominating Set, Domination Number, Upper Domination Number

Explore with Wolfram|Alpha

References

Akbari, S.; Alikhani, S.; and Peng, Y.-H. "Characterization of Graphs Using Domination Polynomials." Eur. J. Combin. 31, 1714-1724, 2010.Alikhani, S. and Peng, Y.-H. "Dominating Sets and Domination Polynomial of Cycles." Global J. Pure Appl. Math. 4, No. 2, 2008.Alikhani, S. and Peng, Y.-H. "Introduction to Domination Polynomial of a Graph." Ars Combin. 114, 257-266, 2014.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-157 and 288, 1983.Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Haynes, T. W.; Hedetniemi, S. T.; and Slater, P. J. Fundamentals of Domination in Graphs. New York: Dekker, 1998.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.Kotek, T.; Preen, J.; Simon, F.; Tittmann, P; and Trinks, M. "Recurrence Relations and Splitting Formulas for the Domination Polynomial." Electron. J. Combin. 19, No. 3, Paper 47, 27 pp., 2012. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p47.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 15 Aug 2024. https://arxiv.org/abs/2408.08053.van Rooij, J. M. M. and Bodlaender, H. L. "Exact Algorithms for Dominating Set." Discr. Appl. Math. 159, 2147-2164, 2011.

Cite this as:

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

Subject classifications