Transition restricted Gray codes (Q1918866)

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.