Metraipolis › archive › dc_60108a138e65

Rainbow Hamiltonian paths in graph collections under edge-size conditions — arXiv:2610.41203

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41203
License (as archived)
CC0-1.0
Archived
2026-11-02T05:00:31.735Z
SHA-256 of the archived text
b40c826adb753b427fc1fe124cc32d9c43471e2ddf610549c1426aae11e60739
Stable URL of this page
https://metraipolis.com/documento/dc_60108a138e65

How to cite

Rainbow Hamiltonian paths in graph collections under edge-size conditions — arXiv:2610.41203 — arXiv (en), https://arxiv.org/abs/2610.41203 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_60108a138e65 (Metraipolis archive dc_60108a138e65, sha256 b40c826adb753b427fc1fe124cc32d9c43471e2ddf610549c1426aae11e60739)
BibTeX
@misc{dc60108a138e65,
  title = {Rainbow Hamiltonian paths in graph collections under edge-size conditions — arXiv:2610.41203},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41203},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_60108a138e65; sha256 b40c826adb753b427fc1fe124cc32d9c43471e2ddf610549c1426aae11e60739},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41203. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Let $\mathbf{G}=\{G_1,\dots,G_{n-1}\}$ be a collection of not necessarily distinct graphs of order $n$ on the same vertex set $V$. A path $P$ with $V(P)\subseteq V$ is called \emph{rainbow} in $\mathbf{G}$, if there exists an injection $\phi\colon E(P)\to [n-1]$ such that $e\in E(G_{\phi(e)})$ for each $e\in E(P)$. In this paper, we show that if $n\ge3$, $e(G_i)> \binom{n-2}{2}+2$ for each $i\in[n-1]$ and $G_j$ is connected for some $j\in[n-1]$, then there exists a rainbow Hamiltonian path in $\mathbf{G}$ unless $n=6$ with $G_1=G_2=\dots=G_{5}\cong K_2\vee 4K_1$, or $n=8$ with $G_1=G_2=\dots=G_{7}\cong K_3\vee 5K_1$. This corrects Theorem 6 in [Graphs Combin., \textbf{41}(6)(2025), 119] and relaxes its hypothesis from requiring all $G_i$ to be connected to only requiring that at least one $G_i$ is connected, where $i\in[n-1]$. Moreover, we show that if $n\ge2$ and $e(G_i)\ge \binom{n-1}{2}$ for each $i\in[n-1]$, then $\mathbf{G}$ contains a rainbow Hamiltonian path unless $G_1=G_2=\dots=G_{n-1}\cong K_{n-1}\cup K_1$, or $n=4$ with $G_1=G_2=G_3\cong K_{1,3}$. As a consequence, Theorem 2 of [Discrete Math., \textbf{347}(2024), 114128] follows immediately.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.41203 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T04:47:57.672Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).