Hamilton transversals in tournaments
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910478430633984 |
|---|---|
| author | Chakraborti, Debsoumya Kim, Jaehoon Lee, Hyunwoo Seo, Jaehyeon |
| author_facet | Chakraborti, Debsoumya Kim, Jaehoon Lee, Hyunwoo Seo, Jaehyeon |
| contents | 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 $\mathbf{T}=\{T_1,\dots,T_m\}$ of not-necessarily distinct tournaments on a common vertex set $V$, an $m$-edge directed graph $\mathcal{D}$ with vertices in $V$ is called a $\mathbf{T}$-transversal if there exists a bijection $ϕ\colon E(\mathcal{D})\to [m]$ such that $e\in E(T_{ϕ(e)})$ for all $e\in E(\mathcal{D})$. We prove that for sufficiently large $m$ with $m=|V|-1$, there exists a $\mathbf{T}$-transversal Hamilton path. Moreover, if $m=|V|$ and at least $m-1$ of the tournaments $T_1,\ldots,T_m$ are assumed to be strongly connected, then there is a $\mathbf{T}$-transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub $\mathbf{H}$-partition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_00912 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hamilton transversals in tournaments Chakraborti, Debsoumya Kim, Jaehoon Lee, Hyunwoo Seo, Jaehyeon Combinatorics 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 $\mathbf{T}=\{T_1,\dots,T_m\}$ of not-necessarily distinct tournaments on a common vertex set $V$, an $m$-edge directed graph $\mathcal{D}$ with vertices in $V$ is called a $\mathbf{T}$-transversal if there exists a bijection $ϕ\colon E(\mathcal{D})\to [m]$ such that $e\in E(T_{ϕ(e)})$ for all $e\in E(\mathcal{D})$. We prove that for sufficiently large $m$ with $m=|V|-1$, there exists a $\mathbf{T}$-transversal Hamilton path. Moreover, if $m=|V|$ and at least $m-1$ of the tournaments $T_1,\ldots,T_m$ are assumed to be strongly connected, then there is a $\mathbf{T}$-transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub $\mathbf{H}$-partition. |
| title | Hamilton transversals in tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2307.00912 |