Back to Search
Start Over
Cycle lengths in randomly perturbed graphs.
- Source :
- Random Structures & Algorithms; Dec2023, Vol. 63 Issue 4, p867-884, 18p
- Publication Year :
- 2023
-
Abstract
- Let G$$ G $$ be an n$$ n $$‐vertex graph, where δ(G)≥δn$$ \delta (G)\ge \delta n $$ for some δ:=δ(n)$$ \delta := \delta (n) $$. A result of Bohman, Frieze and Martin from 2003 asserts that if α(G)=Oδ2n$$ \alpha (G)=O\left({\delta}^2n\right) $$, then perturbing G$$ G $$ via the addition of ωlog(1/δ)δ3$$ \omega \left(\frac{\log \left(1/\delta \right)}{\delta^3}\right) $$ random edges, a.a.s. yields a Hamiltonian graph. We prove several improvements and extensions of the aforementioned result. In particular, keeping the bound on α(G)$$ \alpha (G) $$ as above and allowing for δ=Ω(n−1/3)$$ \delta =\Omega \left({n}^{-1/3}\right) $$, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a pancyclic graph. Moreover, we prove similar results for sparser graphs, and assuming the correctness of Chvátal's toughness conjecture, we handle graphs having larger independent sets. Finally, under milder conditions, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a graph containing an almost spanning cycle. [ABSTRACT FROM AUTHOR]
- Subjects :
- RANDOM graphs
HAMILTONIAN graph theory
RANDOM numbers
SPARSE graphs
INDEPENDENT sets
Subjects
Details
- Language :
- English
- ISSN :
- 10429832
- Volume :
- 63
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Random Structures & Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 173181735
- Full Text :
- https://doi.org/10.1002/rsa.21170