Introduction to Domination Polynomial of a Graph

Abstract

We introduce the domination polynomial of a graph \(G\). The domination polynomial of a graph \(G\) of order \(n\) is defined as \(D(G, x) = \sum_{i=\gamma(G)}^{n} d(G, i)x^i\), where \(d(G, i)\) is the number of dominating sets of \(G\) of size \(i\), and \(\gamma(G)\) is the domination number of \(G\). We obtain some properties of \(D(G, x)\) and its coefficients, and compute this polynomial for specific graphs.