\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for \magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for Bette Bultena and Frank Ruskey, Transition Restricted Gray Codes
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) {\it 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.
\bye