EUVIMEDEUVIMED entdecken
Crossref

Transversal Hamilton Paths and Cycles

Yangyang Cheng, Wanting Sun, Guanghui Wang, Lan Wei

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →