ScholarWorks@Y-Scholar Hub

초록

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