错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Hamilton Transversals in Tournaments

  • Debsoumya Chakraborti,
  • Jaehoon Kim,
  • Hyunwoo Lee,
  • Jaehyeon Seo

摘要

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 \(\textbf{T}=(T_1,\dots ,T_m)\) T = ( T 1 , , T m ) of not-necessarily distinct tournaments on a common vertex set V, an m-edge directed graph \(\mathcal {D}\) D with vertices in V is called a \(\textbf{T}\) T -transversal if there exists a bijection \(\phi :E(\mathcal {D})\rightarrow [m]\) ϕ : E ( D ) [ m ] such that \(e\in E(T_{\phi (e)})\) e E ( T ϕ ( e ) ) for all \(e\in E(\mathcal {D})\) e E ( D ) . We prove that for sufficiently large m with \(m=|V|-1\) m = | V | - 1 , there exists a \(\textbf{T}\) T -transversal Hamilton path. Moreover, if \(m=|V|\) m = | V | and at least \(m-1\) m - 1 of the tournaments \(T_1,\ldots ,T_m\) T 1 , , T m are assumed to be strongly connected, then there is a \(\textbf{T}\) T -transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub \(\textbf{H}\) H -partition.