Cycles in the burnt pancake graph

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

e l l

with

6 l e q e l l l e q n!

. 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

e l l

with

8 l e q e l l l e q 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

n g e q 2

, which are the smallest cycles embeddable in

B P_{n}

, by presenting their canonical forms as products of the prefix reversal generators.

Recommendations

Cites Work

Cited In (18)

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