All Parity Realizable Trees

Abstract

Given a graph $G=(V,E)$ and a vertex subset $D\subseteq V$, a subset $S\subseteq V$ is said to realize a “parity assignment” $D$ if for each vertex $v\in V$ with closed neighborhood $N[v]$ we have that $|N[v]\cap S|$ is odd if and only if $v\in D$. Graph $G$ is called all parity realizable if every parity assignment $D$ is realizable. This paper presents some examples and provides a constructive characterization of all parity realizable trees.