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

Autor:	Dvořák, Tomáš, Gu, Mei-Mei
Rok vydání:	2023
Předmět:	Computer Science - Discrete Mathematics Mathematics - Combinatorics 05C70 05C45 68M10 68R10 G.2.2
Druh dokumentu:	Working Paper
Popis:	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\geq 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\ge3$ there is a set of $n-2$ faulty edges or faulty vertices for which such a fault-free disjoint path cover does not exist. Comment: 14 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2310.18831 Zobrazit plný text záznamu View this record from Arxiv