Hamilton Transversals in Tournaments

It is well-known that every tournament contains a Hamilton path, and every strongly connected tournament contains a Hamilton cycle. This paper establishes transversal generalizations of these classical results. For a collection T=(T₁, ,Tₘ) T = ( T 1 , ⋯ , T m ) of not-necessarily distinct tournaments on a common vertex set V , an m -edge directed graph D D with vertices in V is called a T T -transversal if there exists a bijection φ :E(D)→ [m] ϕ : E ( D ) → [ m ] such that e∈ E(Tφ (e)) e ∈ E ( T ϕ ( e ) ) for all e∈ E(D) e ∈ E ( D ) . We prove that for sufficiently large m with $$m=|V|-1$$ m = | V | - 1 , there exists a T T -transversal Hamilton path. Moreover, if $$m=|V|$$ m = | V | and at least $$m-1$$ m - 1 of the tournaments T₁,… ,Tₘ T 1 , … , T m are assumed to be strongly connected, then there is a T T -transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub H H - partition .