Rainbow Hamiltonicity and the spectral radius
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910782281744384 |
|---|---|
| author | Zhang, Yuke van Dam, Edwin R. |
| author_facet | Zhang, Yuke van Dam, Edwin R. |
| contents | Let $\mathcal{G}=\{G_1,\ldots,G_n \}$ be a family of graphs of order $n$ with the same vertex set. A rainbow Hamiltonian cycle in $\mathcal{G}$ is a cycle that visits each vertex precisely once such that any two edges belong to different graphs of $\mathcal{G}$. We show that if each $G_i$ has more than $\binom{n-1}{2}+1$ edges, then $\mathcal{G}$ admits a rainbow Hamiltonian cycle and pose the problem of characterizing rainbow Hamiltonicity under the condition that all $G_i$ have at least $\binom{n-1}{2}+1$ edges. Towards a solution of that problem, we give a sufficient condition for the existence of a rainbow Hamiltonian cycle in terms of the spectral radii of the graphs in $\mathcal{G}$ and completely characterize the corresponding extremal graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_17845 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rainbow Hamiltonicity and the spectral radius Zhang, Yuke van Dam, Edwin R. Combinatorics Let $\mathcal{G}=\{G_1,\ldots,G_n \}$ be a family of graphs of order $n$ with the same vertex set. A rainbow Hamiltonian cycle in $\mathcal{G}$ is a cycle that visits each vertex precisely once such that any two edges belong to different graphs of $\mathcal{G}$. We show that if each $G_i$ has more than $\binom{n-1}{2}+1$ edges, then $\mathcal{G}$ admits a rainbow Hamiltonian cycle and pose the problem of characterizing rainbow Hamiltonicity under the condition that all $G_i$ have at least $\binom{n-1}{2}+1$ edges. Towards a solution of that problem, we give a sufficient condition for the existence of a rainbow Hamiltonian cycle in terms of the spectral radii of the graphs in $\mathcal{G}$ and completely characterize the corresponding extremal graphs. |
| title | Rainbow Hamiltonicity and the spectral radius |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.17845 |