Graphs induced by Gray codes Original Research Article

We disprove a conjecture of Bultena and Ruskey (Electron. J. Combin. 3 (1996) R11), that all trees which are cyclic graphs of cyclic Gray codes have diameter 2 or 4, by producing codes whose cyclic graphs are trees of arbitrarily large diameter. We answer affirmatively two other questions from (Electron. J. Combin. 3 (1996) R11), showing that strongly Pn×Pn-compatible codes exist and that it is possible for a cyclic code to induce a cyclic digraph with no bidirectional edge. A major tool in these proofs is our introduction of supercomposite Gray codes; these generalize the standard reflected Gray code by allowing shifts. We find supercomposite Gray codes which induce large diameter trees, but also show that many trees are not induced by supercomposite Gray codes. We also find the first infinite family of connected graphs known not to be induced by any Gray code—trees of diameter 3 with no vertices of degree 2.