Recurrence Relations and Splitting Formulas for the Domination Polynomial

  • Tomer Kotek
  • James Preen
  • Frank Simon
  • Peter Tittmann
  • Martin Trinks
Keywords: domination polynomial, recurrence relation, splitting formula


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.

Article Number