zbMATH — the first resource for mathematics

Transition restricted Gray codes. (English) Zbl 0864.05066
Electron. J. Comb. 3, No. 1, Research paper R11, 11 p. (1996); printed version J. Comb. 3, No. 1, 123-133 (1996).
The vertex set of the \(n\)-cube \(Q_n\) consists of all bitstrings of length \(n\) (i.e. \(V(Q_n)=\{\text{x}=(x_1,\dots,x_n)\mid x_i\in\{0,1\}\), \(i\in\{1,\dots,n\}\)) and its edge set \(E(Q_n)\) of all unordered pairs xy, where the bitstrings \(\text{x, y}\in V(Q_n)\) differ in exactly one position; the position of this bit that is different is the transition \(\tau(\text{x, y})\) of the edge \(\text{xy}\in E(Q_n)\) (or between x and y). A Hamiltonian path (Hamiltonian cycle, resp.) \(H\) on \(Q_n\) is called a Gray code (cyclic Gray code, resp.). For a Gray code \(H=\text{x}_1,\dots,\text{x}_N\) (a cyclic Gray code \(H=\text{x}_1,\dots,\text{x}_N\), \(\text{x}_1\), resp.) with \(N=2^n\) its transition sequence (cyclic transition sequence, resp.) is \(\tau(H)=t_1,\dots,t_{N-1}\) (\(\tau(H)=t_1,\dots,t_{N-1},t_N\), resp.) where \(t_i=\tau(\text{x}_i,\text{x}_{i+1})\), \(i=1,\dots,N-1\) (and \(t_N=\tau(\text{x}_N,\text{x}_1)\), resp.). The graph \(G_H\) whose vertex set is \(\{1,\dots,n\}\) and whose edge set is \(\{t_it_{i+1}\mid i=1,\dots,N-2\}\) if \(\tau(H)=t_1,\dots,t_{N-1}\) and \(\{t_it_{i+1}\mid i=1,\dots,N-1\}\) if \(\tau(H)=t_1,\dots,t_{N-1},t_N\) is the graph of transitions of \(H\). For any undirected graph \(G\) with \(V(G)=\{1,\dots,n\}\) a \(G\)-code (cyclic \(G\)-code, resp.) is a Hamiltonian path (Hamiltonian cycle, resp.) \(H\) on \(Q_n\) whose graph of transitions \(G_H\) is a subgraph of \(G\). The diameter of \(G\) is the maximum distance of any two vertices of \(G\). The authors prove the following theorems: (1) For every tree \(T\) of diameter 4, there is a cyclic \(T\)-code. (2) For every tree \(T\) of diameter 3, there does not exist any cyclic \(T\)-code.

05C45 Eulerian and Hamiltonian graphs
94B25 Combinatorial codes
05C38 Paths and cycles
Full Text: EMIS EuDML