Cycles in the burnt pancake graph

DOI10.1016/J.DAM.2019.08.008MaRDI QIDQ2009003zbMATH OpenOpenAlexFDO

Authors Saúl A. Blanco, Charles Buehrle, Akshay Patidar

Publication date 27 November 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Cayley graphsHamiltonian cyclesweakly pancyclicburnt pancake graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30)

Abstract: The pancake graph $P_n$ is the Cayley graph of the symmetric group $S_n$ on $n$ elements generated by prefix reversals. $P_n$ has been shown to have properties that makes it a useful network scheme for parallel processors. For example, it is $(n-1)$-regular, vertex-transitive, and one can embed cycles in it of length $ell$ with $6leqellleqn!$. The burnt pancake graph $B{P}_n$, which is the Cayley graph of the group of signed permutations $B_n$ using prefix reversals as generators, has similar properties. Indeed, $B{P}_n$ is $n$-regular and vertex-transitive. In this paper, we show that $B{P}_n$ has every cycle of length $ell$ with $8leqellleq{2}^{n}n!$. The proof given is a constructive one that utilizes the recursive structure of $B{P}_n$. We also present a complete characterization of all the $8$-cycles in $B{P}_n$ for $ngeq2$, which are the smallest cycles embeddable in $B{P}_n$, by presenting their canonical forms as products of the prefix reversal generators.

Recommendations

• Small cycles in the pancake graph
• Cycles of length seven in the pancake graph
• Cycles of length 9 in the pancake graph
• Independent even cycles in the pancake graph and greedy prefix-reversal Gray codes
• Girth of pancake graphs

Cites work

• A group-theoretic model for symmetric interconnection networks
• A new general family of mixed graphs
• A very elementary presentation of the Hannenhalli-Pevzner theory
• An (18/11)n upper bound for sorting by prefix reversals
• Bounds for sorting by prefix reversal
• Cycles in the burnt pancake graph
• Cycles of length 9 in the pancake graph
• Cycles of length seven in the pancake graph
• Girth of pancake graphs
• On average and highest number of flips in pancake sorting
• On the Diameter of the Pancake Network
• On the embedding of cycles in pancake graphs
• On the problem of sorting burnt pancakes
• Pancyclic graphs. I
• Processor interconnection networks from Cayley graphs
• Ring embedding in faulty pancake graphs
• Small cycles in the pancake graph
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Transforming cabbage into turnip

Cited in

(18)

• Chromatic properties of the Pancake graphs
• Paired 2-disjoint path covers of burnt pancake graphs with faulty elements
• Cyclic Vertex (Edge) Connectivity of Burnt Pancake Graphs
• Cycles of length 9 in the pancake graph
• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Cycles in the burnt pancake graph
• Vulnerability analysis of multiprocessor system based on burnt pancake networks
• Neighbor-connectivity of pancake networks and burnt pancake networks
• Lengths of cycles in generalized pancake graphs
• An Algorithm to Enumerate Grid Signed Permutation Classes
• The structure fault tolerance of burnt pancake networks
• The Cayley network of expanded Pancake graphs
• Some integer values in the spectra of burnt pancake graphs
• Independent even cycles in the pancake graph and greedy prefix-reversal Gray codes
• Girth of pancake graphs
• Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
• Cycles of length seven in the pancake graph
• Small cycles in the pancake graph

This page was built for publication: Cycles in the burnt pancake graph

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