Combinatorial properties of a general domination problem with parity constraints

We consider various properties of a general parity domination problem: given a graph GG on nn vertices, one is looking for a subset SS of the vertex set such that the open/closed neighborhood of each vertex contains an even/odd number of vertices in SS (it is prescribed individually for each vertex which of these applies). We define the parameter s(G)s(G) to be the number of solvable instances out of 4n4n possibilities and study the properties of this parameter. Upper and lower bounds for general graphs and trees are given as well as a remarkable recurrence formula for rooted trees. Furthermore, we give explicit formulas in several special cases and investigate random graphs.