A Gray code is a Hamilton path H on the n-cube, Q(n). By labeling each edge of Q(n) 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, G[H], whose vertices are {1,2,...,n} and with edge set E(G[H]) = { [t(i),t(i+1)] | 1 < i < N-1 }. 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.
Transition Sequence:
10767076567076701210123454323432
12345654567076701076707654567654
32343210123454321012343210121070
12101234321012345432101234321234
56545676545654323456543212343234
54321012343210121070121012345432
34565432123456543234565456765456
54323456543212345654323432107012
Code:
0,2,3,131,195,67,66,194,130,162,226,98,99,227,163,35,
34,32,36,38,39,37,33,41,57,25,9,1,5,13,29,21,
17,19,23,31,15,47,111,79,95,127,63,191,190,62,126,254,
255,253,252,124,60,188,189,61,125,93,77,109,45,173,237,205,
221,213,209,217,201,193,197,199,198,196,192,200,216,248,232,224,
228,230,231,229,225,233,249,241,245,247,246,244,240,242,243,115,
114,112,116,118,119,117,113,121,105,97,101,103,102,100,96,104,
120,88,72,64,68,70,71,69,65,73,89,81,85,87,83,91,
75,107,43,11,27,59,123,251,187,155,139,171,235,203,219,211,
215,223,207,239,175,143,159,151,147,145,149,157,141,133,129,137,
153,185,169,161,165,167,166,164,160,168,184,176,180,182,183,181,
177,179,178,50,51,49,53,55,54,52,48,56,40,8,24,16,
20,28,12,44,108,76,92,84,80,82,86,94,78,110,46,14,
30,22,18,26,10,42,106,74,90,122,58,186,250,218,202,234,
170,138,154,146,150,158,142,174,238,206,222,214,210,208,212,220,
204,236,172,140,156,148,144,152,136,128,132,134,135,7,6,4