Graphs induced by Gray codes

Download: PDF.

“Graphs induced by Gray codes” by Elizabeth L. Wilmer and Michael D. Ernst. Discrete Mathematics, vol. 257, November 28, 2002, pp. 585-598.
A previous version appeared in ALICE03, 1st Workshop on Algorithms for Listing, Counting, and Enumeration, (Baltimore, Maryland), January 11, 2003.


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 (P_n × P_n)-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.

Download: PDF.

BibTeX entry:

   author = {Elizabeth L. Wilmer and Michael D. Ernst},
   title = {Graphs induced by {Gray} codes},
   journal = {Discrete Mathematics},
   volume = {257},
   pages = {585--598},
   month = {November~28,},
   year = {2002}

(This webpage was created with bibtex2web.)

Back to Michael Ernst's publications.