Menu
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’ \) in \( D \) such that the vertex set of \( C’ \) contains the vertex set of \( C \) and \( C’ \) 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’ \) in \( D \) such that the vertex set of \( C’ \) contains the vertex set of \( C \) and \( C’ \) 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.