Name
Abstract | ||
|---|---|---|
Let G(1), ...,G(n), be graphs on the same vertex set of size n, each graph with minimum degree delta(G(i)) >= n/2. A recent conjecture of Aharoni asserts that there exists a rainbow Hamiltonian cycle i.e. a cycle with edge set {e(1),..., e(n)} such that e(i) E E(G(i)) for 1 <= i <= n. This can be viewed as a rainbow version of the well-known Dirac theorem. In this paper, we prove this conjecture asymptotically by showing that for every epsilon > 0, there exists an integer N > 0, such that when n > N for any graphs G(1), ...,G(n), on the same vertex set of size n with delta(G(i)) >= (1/2 + epsilon), there exists a rainbow Hamiltonian cycle. Our main tool is the absorption technique. Additionally, we prove that with delta(G(i)) >= (n+1/2) for each i, one can find rainbow cycles of length 3, ..., n - 1. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.37236/9033 | ELECTRONIC JOURNAL OF COMBINATORICS |
Keywords | DocType | Volume |
Dirac theorem, rainbow Hamiltonian cycle, absorption technique, pancyclicity | Journal | 28 |
Issue | ISSN | Citations |
3 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng Yangyang | 1 | 0 | 0.34 |
| Guanghui Wang | 2 | 199 | 23.23 |
| Yi Zhao | 3 | 40 | 6.92 |