Let be the number of dominating sets of size in a graph , then the domination polynomial of in the variable is defined as
where is the (lower) domination number of (Kotek et al. 2012, Alikhani and Peng 2014).
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 has time complexity (van Rooij and Bodlaender 2011, Mertens 2024).
Precomputed domination polynomials for many named graphs in terms of a variable 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).
graph | |
barbell graph | |
book graph | |
cocktail party graph | |
complete bipartite graph | |
complete graph | |
empty graph | |
helm graph | |
sunlet graph |
The following table summarizes the recurrence relations for domination polynomials for some simple classes of graphs.