A Gray code for the shelling types of the boundary of a hypercube

DOI10.1016/J.DISC.2012.10.011MaRDI QIDQ1928446zbMATH OpenOpenAlexFDO

Authors Sarah Birdsong, Gabor Hetyei

Publication date 3 January 2013

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.4710

zbMATH Keywords

connected permutationsGray codeindecomposable permutations

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph theory (including graph drawing) in computer science (68R10) Combinatorial codes (94B25)

Abstract: We consider two shellings of the boundary of the hypercube equivalent if one can be transformed into the other by an isometry of the cube. We observe that a class of indecomposable permutations, bijectively equivalent to standard double occurrence words, may be used to encode one representative from each equivalence class of the shellings of the boundary of the hypercube. These permutations thus encode the shelling types of the boundary of the hypercube. We construct an adjacent transposition Gray code for this class of permutations. Our result is a signed variant of King's result showing that there is a transposition Gray code for indecomposable permutations.

Review text

Recently, \textit{A. King} [ibid. 306, No. 5, 508--518 (2006; Zbl 1086.05004)] provided a transposition Gray code for the set of all indecomposable permutations of length \(n\). In this article, the authors construct an adjacent transposition Gray code for a signed variant of the indecomposable permutations, called sign-connected permutations of the set \(\{\pm1,\pm 2,\dots,\pm n\}\). These permutations encode the shelling types of the boundary of the hypercube. The author proves that this Gray code can be generated in constant amortized time.

Recommendations

• Note on Gray codes for permutation lists
• Combinatorial generation via permutation languages. I: Fundamentals
• Gray code for permutations with a fixed number of cycles
• Doubly adjacent gray codes for the symmetric group
• Gray code for permutations with a fixed number of left-to-right minima.

Cited in

(3)

• Generating indecomposable permutations
• Note on Gray codes for permutation lists
• Star transposition Gray codes for multiset permutations

This page was built for publication: A Gray code for the shelling types of the boundary of a hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1928446)