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

2023/10/28 by Tomáš Dvořák, Mei-Mei Gu, Dvořák, Tomáš +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #05C45 #05C70 #68M10 #68R10 #Biofuel production and bioconversion #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Genome Rearrangement Algorithms #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2310.18831

openalex publication_date 2023/10/28 · openalex created_date 2023/11/01 · openalex updated_date 2026/07/28

Abstract

The burnt pancake graph BP_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 BP_n for n≥ 4. We show that there are u-v and x-y paths whose vertices partition the vertex set of BP_n even if BP_n 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.

Related

• Cycles in the burnt pancake graphs
• Paired many-to-many 2-disjoint path cover of balanced hypercubes with faulty edges
• Many-to-many disjoint paths in hypercubes with faulty vertices
• The generalized 4-connectivity of burnt pancake graphs
• Path coverings with prescribed ends in faulty hypercubes