On locally-balanced $2$-partitions of some classes of graphs

In this paper we obtain some conditions for the existence of locally-balanced $2$-partitions with an open (with a closed) neighborhood of some classes of graphs. In particular, we give necessary conditions for the existence of locally-balanced $2$-partitions of even and odd graphs. We also obtain some results on the existence of locally-balanced $2$-partitions of rook's graphs and powers of cycles. In particular, we prove that if $m,n\geq 2$, then the graph $K_{m} \Box K_{n}$ has a locally-balanced $2$-partition with a closed neighborhood if and only if $m$ and $n$ are even. Moreover, all our proofs are constructive and provide polynomial time algorithms for constructing the required $2$-partitions.