Abstract 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>T</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of not-necessarily distinct tournaments on a common vertex set V , an m -edge directed graph $$\mathcal {D}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>D</mml:mi> </mml:math> with vertices in V is called a $$\textbf{T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> -transversal if there exists a bijection $$\phi :E(\mathcal {D})\rightarrow [m]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϕ</mml:mi> <mml:mo>:</mml:mo> <mml:mi>E</mml:mi> <mml:mo>(</mml:mo> <mml:mi>D</mml:mi> <mml:mo>)</mml:mo> <mml:mo>→</mml:mo> <mml:mo>[</mml:mo> <mml:mi>m</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> such that $$e\in E(T_{\phi (e)})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>e</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>T</mml:mi> <mml:mrow> <mml:mi>ϕ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>e</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for all $$e\in E(\mathcal {D})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>e</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> <mml:mo>(</mml:mo> <mml:mi>D</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We prove that for sufficiently large m with $$m=|V|-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mo>|</mml:mo> <mml:mi>V</mml:mi> <mml:mo>|</mml:mo> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , there exists a $$\textbf{T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> -transversal Hamilton path. Moreover, if $$m=|V|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mo>|</mml:mo> <mml:mi>V</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:math> and at least $$m-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> of the tournaments $$T_1,\ldots ,T_m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>T</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> </mml:math> are assumed to be strongly connected, then there is a $$\textbf{T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> -transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub $$\textbf{H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> - partition .

Debsoumya Chakraborti

Jaehoon Kim

Hyunwoo Lee

Jaehyeon Seo

COMBINATORICA

COMBINATORICA 在组合学和计算理论的各个领域以英语发表研究论文，特别强调通用技术和统一原则。 COMBINATORICA 涵盖的典型但非排他性主题是 - 组合结构（图、超图、拟阵、设计、排列组）。- 组合优化。- 几何和数论的组合方面。- 组合学和相关领域的算法。- 计算复杂性理论.- 组合学和算法中的随机化和显式构造。

The journal Combinatorica publishes research papers in the fields of combinatorics and computational theory in English, with a particular emphasis on general techniques and unifying principles. Typical, though not exclusive, topics covered include: combinatorial structures (graphs, hypergraphs, matroids, designs, permutations), combinatorial optimization, combinatorial aspects of geometry and number theory, algorithms in combinatorics and related areas, computational complexity theory, and randomization and explicit constructions in combinatorics and algorithms.

《Combinatorica》期刊以英语发表组合学和计算理论领域的研究论文，特别强调通用技术和统一原则。期刊涵盖的主题包括但不限于：组合结构（如图、超图、拟阵、设计、排列组）、组合优化、几何和数论的组合方面、组合学及相关领域的算法、计算复杂性理论，以及组合学和算法中的随机化与显式构造。

Category	Quartile
数学	2
数学, 数学	2

Hamilton Transversals in Tournaments

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info