TOPICS
Search

Domination Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

graphD(x)
barbell graph[-1+(1+x)^n]^2
book graph S_(n+1) square P_2-2x^n+x^2(1+x)^((2n))+[x(2+x)]^n(1+2x)
cocktail party graph K_(n×2)(x+1)^(2n)-2nx-1
complete bipartite graph K_(m,n)[(x+1)^m-1][(1+x)^n-1]+x^m+x^n
complete graph K_n(x+1)^n-1
empty graph K^__nx^n
helm graphx^n[(x+1)(x+2)^n-1]
sunlet graph C_n circledot K_1[x(x+2)]^n

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

graphorderrecurrence
antiprism graph5p_n(x)=x^2p_(n-5)(x)+x^2p_(n-4)(x)+x^2p_(n-3)(x)+(x+2)xp_(n-2)(x)+(x+2)xp_(n-1)(x)
barbell graph3p_n(x)=-(x^2+3x+3)(x+1)p_(n-2)(x)+(x^2+3x+3)p_(n-1)(x)+(x+1)^3p_(n-3)(x)
book graph S_(n+1) square P_23p_n(x)=x^2(x+2)(x+1)^2p_(n-3)(x)+(2x^2+5x+1)p_(n-1)(x)-x(x^3+6x^2+9x+3)p_(n-2)(x)
cocktail party graph K_(n×2)3p_n(x)=-(2x^2+4x+3)p_(n-2)(x)+(x^2+2x+3)p_(n-1)(x)+(x+1)^2p_(n-3)(x)
complete graph K_n2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
cycle graph C_n3p_n(x)=xp_(n-3)(x)+xp_(n-2)(x)+xp_(n-1)(x)
empty graph K^__n1p_n(x)=xp_(n-1)(x)
gear graph6p_n(x)=(x+1)x^4p_(n-6)(x)+(x+2)(2x-1)x^3p_(n-4)(x)+(2x^2+2x-1)x^3p_(n-5)(x)+(x^3+2x^2-3x-2)x^2p_(n-3)(x)-(x^3+6x^2+6x-1)xp_(n-2)(x)+(2x+5)xp_(n-1)(x)
helm graph2p_n(x)=x(x+3)p_(n-1)(x)-x^2(x+2)p_(n-2)(x)
ladder graph P_2 square P_n5p_n(x)=-x^3p_(n-5)(x)-x^3p_(n-4)(x)+(x+1)x^2p_(n-3)(x)+(x+1)xp_(n-2)(x)+(x+2)xp_(n-1)(x)
path graph P_n3p_n(x)=xp_(n-3)(x)+xp_(n-2)(x)+xp_(n-1)(x)
star graph S_n2p_n(x)=(2x+1)p_(n-1)(x)-x(x+1)p_(n-2)(x)
sun graph2p_n(x)=x(x+1)p_(n-2)(x)+x(x+2)p_(n-1)(x)
sunlet graph C_n circledot K_11p_n(x)=x(x+2)p_(n-1)(x)
web graph3p_n(x)=(x+2)^2x^4p_(n-3)(x)+(x+2)x^3p_(n-2)(x)+(x^2+3x+1)xp_(n-1)(x)
wheel graph W_n4p_n(x)=-(x+1)x^2p_(n-4)(x)-(2x+3)x^2p_(n-3)(x)-(x-1)(x+2)xp_(n-2)(x)+(x+3)xp_(n-1)(x)

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