Recurrence Relations and Splitting Formulas for the Domination Polynomial

Tomer Kotek, James Preen, Frank Simon, Peter Tittmann, Martin Trinks


The domination polynomial $D(G,x)$ of a graph $G$ is the generating function of its dominating sets. We prove that $D(G,x)$ satisfies a wide range of reduction formulas. We show linear recurrence relations for $D(G,x)$ for arbitrary graphs and for various special cases. We give splitting formulas for $D(G,x)$ based on articulation vertices, and more generally, on splitting sets of vertices.


domination polynomial; recurrence relation; splitting formula

Full Text: PDF