A Hamilton Cycle in the k-Sided Pancake Network

2021/03/16 by Cameron, Ben, Sawada, Joe, Williams, Aaron
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2103.09256

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 π= p₁p₂⋯ p_n, where each p_i has an associated colour in \0,1,…, k-1\. There is a directed edge (π₁,π₂) if π₂ can be obtained from π₁ 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.

Related

• Hamilton cycles in a semi-random graph model
• Cycles in the burnt pancake graphs
• Pancyclicity of Hamiltonian graphs
• Colour-biased Hamilton cycles in random graphs
• Low independence number and Hamiltonicity implies pancyclicity