Transition Restricted Gray Codes

  • Bette Bultena
  • Frank Ruskey


A Gray code is a Hamilton path $H$ on the $n$-cube, $Q_n$. By labeling each edge of $Q_n$ with the dimension that changes between its incident vertices, a Gray code can be thought of as a sequence $H = t_1,t_2,\ldots,t_{N-1}$ (with $N = 2^n$ and each $t_i$ satisfying $1 \le t_i \le n$). The sequence $H$ defines an (undirected) graph of transitions, $G_H$, whose vertex set is $\{1,2,\ldots,n\}$ and whose edge set $E(G_H) = \{ [t_i,t_{i+1}] \mid 1 \le i \le N-1 \}$. A $G$-code is a Hamilton path $H$ whose graph of transitions is a subgraph of $G$; if $H$ is a Hamilton cycle then it is a cyclic $G$-code. The classic binary reflected Gray code is a cyclic $K_{1,n}$-code. We prove that every tree $T$ of diameter 4 has a $T$-code, and that no tree $T$ of diameter 3 has a $T$-code.

Article Number