Transition Restricted Gray Codes

A Gray code is a Hamilton path H on the n-cube, Qn . By labeling each edge of Qn with the dimension that changes between its incident vertices, a Gray code can be thought of as a sequence H = t 1 ; t 2 ; : : : ; t N-1 (with N = 2 n and each t i satisfying 1 t i n). The sequence H defines an (undirected) graph of transitions, GH , whose vertices are f1; 2; : : : ; ng and with edge set E(GH ) = f[t i ; t i+1 ] j 1 i N - 1g. 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. 1 Introduction The utility of the ubiquitous binary reflected Gray code is undisputed. See, for example, the books of Nijenhuis and Wilf [5], Reingold, Nievergelt, and Deo [6], and Wilf [8]. For certain applications, however, other Gray codes are desired. Many other..