Odd and Even Dominating Sets with Open Neighborhoods

Abstract

A subset \(D\) of the vertex set \(V\) of a graph is called an open odd dominating set if each vertex in \(V\) is adjacent to an odd number of vertices in \(D\) (adjacency is irreflexive). In this paper we solve the existence and enumeration problems for odd open dominating sets (and analogously defined even open dominating sets) in the \(m \times n\) grid graph and prove some structural results for those that do exist. We use a combination of combinatorial and linear algebraic methods, with particular reliance on the sequence of Fibonacci polynomials over \({GF}(2)\).