Paired 2-disjoint path covers of burnt pancake graphs with faulty elements

Abstract

The burnt pancake graph $B{P}_n$ is the Cayley graph of the hyperoctahedral group using prefix reversals as generators. Let $\{u,v\}$ and $\{x,y\}$ be any two pairs of distinct vertices of $B{P}_n$ for $n\ge 4$. We show that there are $u-v$ and $x-y$ paths whose vertices partition the vertex set of $B{P}_n$ even if $B{P}_n$ has up to $n-4$ faulty elements. On the other hand, for every $n\ge 3$ there is a set of $n-2$ faulty edges or faulty vertices for which such a fault-free disjoint path cover does not exist.

14 pages, 4 figures