Speaker:
Elena Konstantinova
- Russian Academy of Sciences and Novosibirsk State University
Tuesday, May 10, 2016
at
2:30 PM
rinfresco 14:15, inizio seminario 14.30
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.
- Place
-
Ca' Vignal - Piramide,
Floor 0,
Hall Verde
- Programme Director
-
Zsuzsanna
Liptak
-
External reference
-
- Publication date
-
March 15, 2016
