MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


          K3
The $3$-path starting with $(1,0,0)$ goes in three steps to $(0,0,0)$ and then is stable:
          P3
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:
          Y
(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.


Added animation just for fun:
          BlinkWheels
          (Bit assignment thanks to Tony Huynh.)


share|cite|improve this question
4  
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
1  
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
up vote 10 down vote accepted

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.

share|cite|improve this answer
    
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$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.