Transversal Hamilton Paths and Cycles
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1168-1205
DOI: 10.1137/24m1675011 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 24.07.2026. Verfasst von Yangyang Cheng und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 47 Literaturangaben. Gefördert von: National Key Research and Development Program of China, Natural Science Foundation of Shandong Province, China Postdoctoral Science Foundation.
Abstract (Originalsprache)
Given a collection [Formula: see text] of graphs on the common vertex set [Formula: see text] of size [Formula: see text], an [Formula: see text]-edge graph [Formula: see text] with vertices in [Formula: see text] is a transversal in [Formula: see text] if there exists a bijection [Formula: see text] such that [Formula: see text] for all [Formula: see text]. Denote [Formula: see text]. In this paper, we first establish a minimum degree condition for the existence of transversal Hamilton paths in [Formula: see text]: if [Formula: see text] and [Formula: see text], then [Formula: see text] contains a transversal Hamilton path. This solves a problem proposed by [L. Li, P. Li, and X. Li, J. Graph Theory, 104 (2023), pp. 341–359]. As a continuation of the transversal version of Dirac’s theorem [F. Joos and J. Kim, Bull. Lond. Math. Soc., 52 (2020), 498–504] and the stability result for transversal Hamilton cycles [Y. Cheng and K. Staden, Electron. J. Combin., 32 (2025), P4.36], our second result characterizes all graph collections with minimum degree at least [Formula: see text] and without transversal Hamilton cycles. We obtain an analogous result for transversal Hamilton paths. The proof is a combination of the stability result for transversal Hamilton paths and cycles and the transversal blow-up lemma, along with some structural analysis.
Förderung
- National Key Research and Development Program of China
- Natural Science Foundation of Shandong Province
- China Postdoctoral Science Foundation
- European Research Council
- National Natural Science Foundation of China
Zitieren
APA
Cheng, Y., Sun, W., Wang, G., & Wei, L. (2026). Transversal Hamilton Paths and Cycles. SIAM Journal on Discrete Mathematics, 40(3), 1168-1205. https://doi.org/10.1137/24m1675011
Vancouver
Cheng Y, Sun W, Wang G, Wei L. Transversal Hamilton Paths and Cycles. SIAM Journal on Discrete Mathematics. 2026;40(3):1168-1205. doi:10.1137/24m1675011
BibTeX
@article{Cheng2026,
author = {Cheng, Yangyang and Sun, Wanting and Wang, Guanghui and Wei, Lan},
title = {Transversal Hamilton Paths and Cycles},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {1168--1205},
doi = {10.1137/24m1675011}
}
EUVIMED