### Abstract

An n-bit Gray code is a circular listing of all 2^{n} n-bit binary strings in which consecutive strings differ at exactly one bit. For n ≤ t ≤ 2^{n - 1}, an (n, t)-antipodal Gray code is a Gray code in which the complement of any string appears t steps away from the string, clockwise or counterclockwise. Killian and Savage proved that an (n, n)-antipodal Gray code exists when n is a power of 2 or n = 3, and does not exist for n = 6 or odd n > 3. Motivated by these results, we prove that for odd n ≥ 3, an (n, t)-antipodal Gray code exists if and only if t = 2^{n - 1} - 1. For even n, we establish two recursive constructions for (n, t) codes from smaller (n^{′}, t^{′}). Consequently, various (n, t)-antipodal Gray codes are found for even n's. Examples are for t = 2^{n - 1} - 2^{k} with k odd and 1 ≤ k ≤ n - 3 when n ≥ 4, for t = 2^{n - k} when n ≥ 2 k with 1 ≤ k ≤ 3, for t = n when n = 2^{k} ≥ 2 (an alternative proof for Killian and Savage's result) ...etc.

Original language | English |
---|---|

Pages (from-to) | 82-90 |

Number of pages | 9 |

Journal | Theoretical Computer Science |

Volume | 374 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 2007 Apr 20 |

### Fingerprint

### Keywords

- Antipodal
- Complement
- Gray code
- Hamiltonian cycle
- Period
- n-cube

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Theoretical Computer Science*,

*374*(1-3), 82-90. https://doi.org/10.1016/j.tcs.2006.12.005