On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
Authors:
- Sonny Ben-ShimonSBSonny Ben-Shimon
- Michael KrivelevichMKMichael Krivelevich
- Benny SudakovBSBenny Sudakov
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 25 (3) , 1176-1193
Abstract
Let [Formula: see text] be a sequence of [Formula: see text] integers. For an increasing monotone graph property [Formula: see text] we say that a base graph [Formula: see text] is [Formula: see text]-resilient with respect to [Formula: see text] if for every subgraph [Formula: see text] such that [Formula: see text] for every [Formula: see text] the graph [Formula: see text] possesses [Formula: see text]. This notion naturally extends the idea of the local resilience of graphs recently initiated by Sudakov and Vu. In this paper we study the [Formula: see text]-resilience of a typical graph from [Formula: see text] with respect to the Hamiltonicity property, where we let [Formula: see text] range over all values for which the base graph is expected to be Hamiltonian. Considering this generalized approach to the notion of resilience our main result implies several corollaries which improve on the best known bounds of Hamiltonicity related questions. For one, it implies that for every positive [Formula: see text] and large enough values of [Formula: see text], if [Formula: see text], then with high probability the local resilience of [Formula: see text] with respect to being Hamiltonian is at least [Formula: see text], improving on the previous bound for this range of [Formula: see text]. Another implication is a result on optimal packing of edge-disjoint Hamilton cycles in a random graph. We prove that if [Formula: see text], then with high probability a graph [Formula: see text] sampled from [Formula: see text] contains [Formula: see text] edge-disjoint Hamilton cycles, extending the previous range of [Formula: see text] for which this was known to hold.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular GraphsCombinatorics, Probability and Computing, 2010
- Local resilience of almost spanning trees in random graphsRandom Structures & Algorithms, 2010
- Increasing the chromatic number of a random graphJournal of Combinatorics, 2010
- Resilient Pancyclicity of Random and Pseudorandom GraphsSIAM Journal on Discrete Mathematics, 2010
- On two Hamilton cycle problems in random graphsIsrael Journal of Mathematics, 2008
- On the Resilience of Long Cycles in Random GraphsThe Electronic Journal of Combinatorics, 2008
- On packing Hamilton cycles in -regular graphsJournal of Combinatorial Theory, Series B, 2005
- Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular GraphsJournal of Combinatorial Theory, Series B, 2001
- Almost all Regular Graphs are HamiltonianEuropean Journal of Combinatorics, 1983
- Limit distribution for the existence of hamiltonian cycles in a random graphDiscrete Mathematics, 1983