-
Tomer Kotek
-
James Preen
-
Frank Simon
-
Peter Tittmann
-
Martin Trinks
Keywords:
domination polynomial, recurrence relation, splitting formula
Abstract
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.