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

Abstract

The burnt pancake graph BPn 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 BPn for n>=4.

We show that there are u-v and x-y paths whose vertices partition the vertex set of BPn even if BPn has up to n-4 faulty elements. On the other hand, for every n>=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.

Keywords

• Burnt pancake graphs
• Disjoint path cover
• Faulty elements
• Hamiltonian path