Graphs induced by Gray codes
Submitted by mernst on Wed, 2011-11-30 14:35
| Title | Graphs induced by Gray codes |
| Publication Type | Journal Article |
| Year of Publication | 2002 |
| Authors | Wilmer EL, Ernst MD |
| Journal | Discrete Mathematics |
| Volume | 257 |
| Pagination | 585–598 |
| Date or Month Published | November 28 |
| Abstract | <p>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 \times P_n)$-compatible codes exist and that it is possible for a cyclic code to induce a cyclic digraph with no bidirectional edge. </p> <p> A major tool in these proofs is our introduction of <em>supercomposite</em> 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. </p> <p> 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.</p> |
| Citation Key | WilmerE02 |
Last changed Mon, 2013-06-03 10:27

cs.