Skip to main content
2 of 3
added 263 characters in body
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Blinking graphs

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][1]][1]
The $3$-path starting with $(1,0,0)$ goes in three steps to $(0,0,0)$ and then is stable:
          [![P3][2]][2]
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][3]][3]
(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][4]][4]
          (Bit assignment thanks to Tony Huynh.)
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958