Graphs induced by Gray codes
type: Item
instance of: scholarly article
title: Graphs induced by Gray codes
zbMATH Open document ID: 1009.05094
DOI: 10.1016/S0012-365X(02)00516-2
author: Elizabeth L. Wilmer
author: Michael D. Ernst
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: 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.
reviewed by: Bai Kishan Dass
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1839016
zbMATH Keywords: strings
zbMATH Keywords: Hamilton cycles
zbMATH Keywords: Gray codes
zbMATH Keywords: trees
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1839016