Key points are not available for this paper at this time.
Given a collection G =\G₁, G₂, , Gₘ\ of graphs on the common vertex set V of size n, an m-edge graph H on the same vertex set V is transversal in G if there exists a bijection: E (H) m such that e E (G (₄) ) for all e E (H). Denote (G): =*min\ (Gᵢ): i m\. In this paper, we first establish a minimum degree condition for the existence of transversal Hamilton paths in G: if n=m+1 and (G) n-12, then G contains a transversal Hamilton path. This solves a problem proposed by Li, Li and Li, J. Graph Theory, 2023. As a continuation of the transversal version of Dirac's theorem Joos and Kim, Bull. Lond. Math. Soc. , 2020 and the stability result for transversal Hamilton cycles Cheng and Staden, arXiv: 2403. 09913v1, our second result characterizes all graph collections with minimum degree at least n2-1 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 or cycles, transversal blow-up lemma, along with some structural analysis.
Building similarity graph...
Analyzing shared references across papers
Loading...
Cheng et al. (Thu,) studied this question.
www.synapsesocial.com/papers/68e6404bb6db6435875d202d — DOI: https://doi.org/10.48550/arxiv.2406.13998
Y. Cheng
Wanting Sun
Guanghui Wang
Building similarity graph...
Analyzing shared references across papers
Loading...