A Hamilton Cycle in the $k$-Sided Pancake Network

Abstract

We present a Hamilton cycle in the $k$-sided pancake network and four combinatorial algorithms to traverse the cycle. The network's vertices are coloured permutations $\pi =p_1{p}_2\cdots p_n$, where each $p_i$ has an associated colour in $\{0,1,\dots ,k-1\}$. There is a directed edge $({\pi }_1,{\pi }_2)$ if ${\pi }_2$ can be obtained from ${\pi }_1$ by a "flip" of length $j$, which reverses the first $j$ elements and increments their colour modulo $k$. Our particular cycle is created using a greedy min-flip strategy, and the average flip length of the edges we use is bounded by a constant.