Transition restricted Gray codes
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.
- On the \((n,t)\)-antipodal Gray codes
- Gray codes with restricted density
- Linear time construction of a compressed Gray code
- Antipodal Gray codes
- Graphs induced by Gray codes
- On the spectrum of Hamiltonian cycles in the \(n\)-cube
- Gray codes and symmetric chains
- On the possibility of an Euler tour representation by Gray codes
- scientific article; zbMATH DE number 17941 (Why is no real title available?)
- scientific article; zbMATH DE number 637346 (Why is no real title available?)
- Gray codes with bounded weights
- Gray codes and symmetric chains
- Some classes of bipartite graphs induced by Gray codes
- Hamiltonian surfaces in the 4-cube, 4-bit Gray codes and Venn diagrams
- Matchings in hypercubes extend to long cycles
- A note on Beckett-Gray codes and the relationship of Gray codes to data structures
- A construction of Gray codes inducing complete graphs
This page was built for publication: Transition restricted Gray codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1918866)
