Transition Restricted Gray Codes

Abstract:

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

• The postscript file is 264,861 bytes, the dvi file is 34,000 bytes.
• Appears in Electronic Journal of Combinatorics, Volume 3 (1996), paper R11.
• For further results on this topic see the paper ``Graphs induced by Gray codes'' by Elizabeth L. Wilmer and Michael D. Ernst. Discrete Mathematics, vol. 257, November 28, 2002, pp. 585-598. There they note a couple of earlier references to the problem by Peter Slater that we missed:
  (a) Open problem, in: Proc. 10th Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Utilitas Mathematica Publishing, Winnipeg, 1979) 918--919,
  (b) Research Problems 109 and 110, Discrete Math. 76 (1989) 293--294.
• E-mail message from Mark Cooke (December 1, 2002) reports on the following Gray code whose transition graph is an 8-cycle.

  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


• Gerard J. Chang, Sen-Peng Eu, and Chung-Heng Yeh, On the (n,t)-antipodal Gray codes, Theoretical Computer Science, 374 (2007) 82-90.
• Charles E. Killian and Carla D. Savage, Antipodal Gray codes, Discrete Mathematics, 281 (2004) 221-236.