Name
Abstract | ||
|---|---|---|
We investigate the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. For all integers k > 1 , r > 0, and l > ( r + 1 ) r, and for any alpha > k k + 1 we show that adding O ( n 2 - 2 / l ) random edges to an n-vertex graph G with minimum degree at least alpha n yields, with probability close to one, the existence of the ( k l + r )-th power of a Hamiltonian cycle. In particular, for r = 1 and l = 2 this implies that adding O ( n ) random edges to such a graph G already ensures the ( 2 k + 1 )-st power of a Hamiltonian cycle (proved independently by Nenadov and Trujic). In this instance and for several other choices of k , l, and r we can show that our result is asymptotically optimal. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1002/jgt.22691 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
augmented graphs, powers of Hamilton cycles | Journal | 98 |
Issue | ISSN | Citations |
2 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Antoniuk Sylwia | 1 | 0 | 0.34 |
| Andrzej Dudek | 2 | 114 | 23.10 |
| Reiher Christian | 3 | 0 | 0.68 |
| Ruciński Andrzej | 4 | 0 | 0.68 |
| Mathias Schacht | 5 | 361 | 37.90 |