Cycle Extendability in Tournaments

Abstract

Let $D$ be a digraph on $n$ vertices. A cycle $C$ in $D$ is said to be 1-extendable if there exists a cycle $C^{\prime }$ in $D$ such that the vertex set of $C^{\prime }$ contains the vertex set of $C$ and $C^{\prime }$ contains exactly one additional vertex. A digraph is 1-cycle-extendable if every non-Hamiltonian cycle is 1-extendable.

A cycle $C$ in $D$ is said to be 2-extendable if there exists a cycle $C^{\prime }$ in $D$ such that the vertex set of $C^{\prime }$ contains the vertex set of $C$ and $C^{\prime }$ contains exactly two additional vertices. A digraph is 2-cycle-extendable if every cycle on at most $n-2$ vertices is 2-extendable.

A digraph is 1,2-cycle-extendable if every non-Hamiltonian cycle is either 1-extendable or 2-extendable. It has been previously shown that not all strong tournaments (orientations of a complete undirected graph) are 1-extendable, but are 2-extendable. The structure of all non 1-extendable tournaments is shown as a type of block Kronecker product of 1-extendable subtournaments.