Greedy prefix-reversal Gray codes and beyond

Elena Konstantinova - Russian Academy of Sciences and Novosibirsk State University
Date and time
Tuesday, May 10, 2016 at 2:30 PM - rinfresco 14:15, inizio seminario 14.30
Ca' Vignal - Piramide, Floor 0, Hall Verde
Programme Director
Zsuzsanna Liptak
External reference
Publication date
March 15, 2016
Computer Science  


In this talk, generalized Gray codes for the Pancake graph are considered. The Pancake graph is a Cayley graph on the symmetric group S_n generated by prefix-reversals. The notion of the Prefix-reversal Gray code as a class was first introduced in 2013 by A. Williams and J. Sawada, and was suggested as a Hamiltonian cycle algorithm in the Pancake graph. The hamiltonicity of the Pancake graph was known since 1984, when S. Zaks has introduced the algorithm of successive generation of permutations by suffix-reversals, which are obviously isomorphic to prefix-reversals. It is known also that there are all cycles of length  6 <= l <= n!, but there are no cycles of length 3,4 or 5 in the Pancake graph. We present the new concept of Prefix-reversal Gray codes based on independent cycles which extends the known greedy Prefix-reversal Gray code constructions given by Zaks and Williams. Cases of non-existence of codes based on the presented family of independent cycles are provided using the fastening cycle approach. We also give necessary condition for existence of greedy Prefix-reversal Gray codes based on the independent cycles with arbitrary even lengths. Some open questions are discussed.


© 2002 - 2021  Verona University
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234