Elizabeth L. Wilmer and Michael D. Ernst
A binary Gray code on n bits induces a graph with vertex set {1, 2, ..., n} in the following way: connect i and j exactly when bit positions i and j change consecutively at some point during the code. Little is known about which graphs occur as induced graphs of Gray codes. We offer several partial results.
We show that trees of diameter 3 without vertices of degree 2 are not graphs of Gray codes.
Generalizing the standard reflected Gray code by allowing shifts yields supercomposite Gray codes, many of which induce trees. We construct supercomposite Gray codes which induce large diameter trees and use them to find Gray codings of grid graphs. We also show that many trees, including paths of length greater than 6, do not have supercomposite Gray codes.
The digraph of a Gray code has as its edges the ordered pairs of bits changing consecutively during the code. We construct a family of cyclic Gray codes whose digraphs contain no bidirectional edges.
We also catalogue the Gray-codability of all graphs on 7 vertices.
CONE April 2000.