Graphs induced by Gray codes (Q1850036)

This paper introduces ``supercomposite Gray codes'' which are a generalization of standard reflected Gray codes by allowing shifts. Using this, the authors disprove a conjecture of Bultena and Ruskey, viz. all trees induced by cyclic Gray codes have diameter \(2\) or \(4\). This has been done by finding supercomposite codes whose cyclic graphs are trees of arbitrary large diameter. In another section, the authors have constructed a family of cyclic Gray codes whose cyclic digraphs contain no bidirectional edges. 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\)---has also been found out and discussed.