# 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.

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