Odd and residue domination numbers of a graph (Q2773048)

A set of vertices \(D\) of a graph \(G\) is called an odd (even) dominating set if \(D\) intersects the closed neighborhood of every vertex of \(G\) in an odd (even) number of elements. The minimum cardinality of an odd (even) dominating set is called the odd (even) domination number of \(G\). This concept of parity domination is generalized to residue domination and several results concerning residue domination for complements of powers of cycles are presented. The odd domination number of a \(2d\)-dimensional cube is shown to be equal to \(2^{2d}\). Moreover the authors show that deciding if a planar graph \(G\) contains an odd dominating set of size at most \(k\) is NP-complete, even if \(G\) has maximum degree six or is bipartite. The paper closes with several open problems.