For any simple graph $G$, assign its nodes a weight/bit of $0$ or $1$. Call this a bit assignment for $G$. Now, generate a new bit assignment as follows: Each node $x$'s bit is replaced by $1$ if the sum of the bits of $x$'s neighbors is odd, and $0$ if that sum is even. For example, the $3$-cycle $K_3$ with bits $(1,0,0)$ goes to $(0,1,1)$ and then is stable:

The $3$-path starting with $(1,0,0)$ goes in three steps to $(0,0,0)$ and then is stable:

Say that $G$ has a blinking assignment if there is a bit assignment that flips to its complement in one step, and then returns to the original assigment, forming a cycle of length two:

(If animated, the graph would "blink.")

Q. Which graphs have blinking assignments?

For example, $K_3$ has no blinking assignment, but the star $S_k$ for $k$ odd does. Many other questions could be asked (e.g., concerning longer cycles), but I'll focus on the above for now.

Because the update rule is to replace a node's weight with the sum of its neighbors' weights $\bmod 2$, it seems possible this process has been studied for some $\mathbb{Z}_n$. If so, I would appreciate a pointer.

(Bit assignment thanks to Tony Huynh.)

-
On a regular lattice, this is sometimes called the XOR cellular automaton. It forms characteristic fractals (Sierpinski triangle on $\mathbb{Z}$) in its space-time trajectories. – Algernon Feb 8 at 21:05
Just a rather obvious remark, a blinking assignment can also be identified by a partitioning of the vertex set into two parts $A$ and $B$ such that each vertex in $A$ has even number of neighbours in $A$ and odd number of neighbours in $B$, and similarly, each vertex in $B$ has even number of neighbours in $B$ and odd number of neighbours in $A$. – Algernon Feb 8 at 21:21

This question seems quite similar to the problem of parity domination. Let $S$ be the set of vertices with label $1$. The condition that $S$ flips to its complement after updating is equivalent to the condition that $|N[v] \cap S|$ is odd for all $v \in V(G)$, where $N[v] = N(v) \cup \{v\}$. Such a set is called an odd dominating set, and it was proved by Sutner that every graph has such a set. In fact, Sutner's proof involved considering a similar CA. See, e.g., this paper for more about parity domination, or see here for Sutner's article.

Asking whether $G$ has a blinking assignment, then, is equivalent to asking whether $G$ has an odd dominating set whose complement is also an odd dominating set. Writing $d_S[v]$ and $d_{G-S}[v]$ for the size of $N[v] \cap S$ and $N[v] \cap (V(G)-S)$ respectively, we need that for every $v \in V(G)$, the quantities $d_S[v]$ and $d_{G-S}[v]$ are both odd. Since $d_S[v] + d_{G-S}[v] = d(v) + 1$, this means every vertex of $G$ needs to have odd degree. On the other hand, if every vertex of $G$ has odd degree, then any odd dominating set should do the trick, and we're guaranteed that one exists.

So, I believe that $G$ should have a blinking assignment if and only if all its vertices have odd degree.

-
Thanks for this clean answer, connecting to dominating sets. – Joseph O'Rourke Feb 9 at 11:14

Here is an exact characterization of the graphs with blinking assignments. Let $H$ be an arbitrary bipartite graph with all vertices having odd degree. Let $(X,Y)$ be a bipartition of $H$. Now add edges to $H$ to form a new graph $G$ such that all vertices in $G[X]$ and $G[Y]$ have even degree. A graph constructed in this way has a blinking assignment; namely all vertices in $X$ are assigned $0$ and all vertices in $Y$ are assigned $1$.

Conversely, every graph with a blinking assignment is constructed in this way. Let $G$ be a graph with a blinking assignment and let $X$ be the vertices of weight $0$ and $Y$ be the vertices with weight $1$. Since zeros become ones, each vertex in $X$ has an odd number of neighbours in $Y$. Since ones become zeros, each vertex in $Y$ has an even number of neighbours in $Y$. Repeating the argument for the second iteration, we have that each vertex in $Y$ has an odd number of neighbours in $X$, and each vertex in $X$ has an even number of neighbours in $X$.

-