Charles Explorer logo
🇨🇿

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

Publikace na Matematicko-fyzikální fakulta |
2024

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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.