Transition restricted Gray codes

Bette Bultena ; Frank Ruskey

The electronic journal of combinatorics, Tome 3 (1996) no. 1

Résumé

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.

Détail

DOI : 10.37236/1235

Classification : 05C45, 94B25, 05C38
Mots-clés : Hamiltonian cycle, \(n\)-cube, Hamiltonian path, Gray code, transition sequence, \(G\)-code, diameter, distance, tree