Transversal Hamilton paths and cycles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911927215587328 |
|---|---|
| author | Cheng, Yangyang Sun, Wanting Wang, Guanghui Wei, Lan |
| author_facet | Cheng, Yangyang Sun, Wanting Wang, Guanghui Wei, Lan |
| contents | Given a collection $\mathcal{G} =\{G_1,G_2,\dots,G_m\}$ 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 $\mathcal{G}$ if there exists a bijection $φ:E(H)\rightarrow [m]$ such that $e \in E(G_{φ(e)})$ for all $e\in E(H)$. Denote $δ(\mathcal{G}):=\operatorname*{min}\left\{δ(G_i): i\in [m]\right\}$. In this paper, we first establish a minimum degree condition for the existence of transversal Hamilton paths in $\mathcal{G}$: if $n=m+1$ and $δ(\mathcal{G})\geq \frac{n-1}{2}$, then $\mathcal{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 $\frac{n}{2}-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13998 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Transversal Hamilton paths and cycles Cheng, Yangyang Sun, Wanting Wang, Guanghui Wei, Lan Combinatorics 05C35 Given a collection $\mathcal{G} =\{G_1,G_2,\dots,G_m\}$ 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 $\mathcal{G}$ if there exists a bijection $φ:E(H)\rightarrow [m]$ such that $e \in E(G_{φ(e)})$ for all $e\in E(H)$. Denote $δ(\mathcal{G}):=\operatorname*{min}\left\{δ(G_i): i\in [m]\right\}$. In this paper, we first establish a minimum degree condition for the existence of transversal Hamilton paths in $\mathcal{G}$: if $n=m+1$ and $δ(\mathcal{G})\geq \frac{n-1}{2}$, then $\mathcal{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 $\frac{n}{2}-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. |
| title | Transversal Hamilton paths and cycles |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2406.13998 |