4-Arc-Pancyclicity of Regular Multipartite Tournaments

Source abstract

A multipartite tournament is an orientation of a complete multipartite graph. We prove that every $r$-regular $c$-partite tournament with common partite-set cardinality $α$ is $4$-arc-pancyclic whenever $c\ge93$; that is, every arc belongs to a cycle of each length from $4$ to $cα$. This confirms the conjecture of Zhou and Zhang for all sufficiently large $c$ and provides a multipartite analog of Alspach's arc-pancyclicity theorem. Moreover, we also give a construction to show that 4-arc-pancyclic is the best possible. Next, we prove that every arc belongs to at least $cα-α-1$ cycles of pairwise distinct lengths when $c\ge7$ and $α\ge2$. For regular $3$-partite tournaments with common partite-set cardinality $α\ge2$, we obtain the sharp lower bound $α$, settling the remaining case of a conjecture of Xia, Cai, Guo, and Wang.