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


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

Precomputed dominations 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


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.Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.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.

Cite this as:

Weisstein, Eric W. "Domination Polynomial." From MathWorld--A Wolfram Web Resource.

Subject classifications