Cycle lengths in randomly perturbed graphs

DOI10.1002/RSA.21170MaRDI QIDQ6063344zbMATH OpenFDO

Authors Elad Aigner-Horev, Dan Hefetz, Michael Krivelevich

Publication date 7 November 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.12210

zbMATH Keywords

cycle lengthsHamiltonicityindependence numberpancyclicityrandomly perturbed graphstoughness

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: Let $G$ be an $n$-vertex graph, where $delta(G)geqdeltan$ for some $delta:=delta(n)$. A result of Bohman, Frieze and Martin from 2003 asserts that if $alpha(G)=Oleft(delt{a}^{2}night)$, then perturbing $G$ via the addition of $omegaleft(fraclog(1/delta)delt{a}^{3}ight)$ random edges, asymptotically almost surely (a.a.s. hereafter) results in a Hamiltonian graph. This bound on the size of the random perturbation is only tight when $delta$ is independent of $n$ and deteriorates as to become uninformative when $delta=Omegaleft(n^{-1/3}ight)$. We prove several improvements and extensions of the aforementioned result. First, keeping the bound on $alpha(G)$ as above and allowing for $delta=Omega(n^{-1/3})$, we determine the correct order of magnitude of the number of random edges whose addition to $G$ a.a.s. results in a pancyclic graph. Our second result ventures into significantly sparser graphs $G$; it delivers an almost tight bound on the size of the random perturbation required to ensure pancyclicity a.a.s., assuming $delta(G)=Omegaleft((alpha(G)logn{)}^{2}ight)$ and $alpha(G)delta(G)=O(n)$. Assuming the correctness of Chv'atal's toughness conjecture, allows for the mitigation of the condition $alpha(G)=Oleft(delt{a}^{2}night)$ imposed above, by requiring $alpha(G)=O(delta(G))$ instead; our third result determines, for a wide range of values of $delta(G)$, the correct order of magnitude of the size of the random perturbation required to ensure the a.a.s. pancyclicity of $G$. For the emergence of nearly spanning cycles, our fourth result determines, under milder conditions, the correct order of magnitude of the size of the random perturbation required to ensure that a.a.s. $G$ contains such a cycle.

Recommendations

• Hamiltonicity of graphs perturbed by a random regular graph
• Random perturbation of sparse graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Pancyclic Hamilton cycles in random graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs

Cites work

• A note on Hamiltonian circuits
• Adding random edges to dense graphs
• An algorithm for finding hamilton cycles in random directed graphs
• An improved linear edge bound for graph linkages
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Graph minors. XIII: The disjoint paths problem
• Hamilton -cycles in randomly perturbed hypergraphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian circuits in random graphs
• Hamiltonicity in randomly perturbed hypergraphs
• Highly linked graphs
• How many random edges make a dense graph hamiltonian?
• How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 17673 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• scientific article; zbMATH DE number 3216216 (Why is no real title available?)
• Introduction to Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Long paths and Hamiltonicity in random graphs
• Longest cycles in sparse random digraphs
• Pancyclic graphs. I
• Pancyclicity of Hamiltonian and highly connected graphs
• Powers of Hamiltonian cycles in randomly augmented graphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Random perturbation of sparse graphs
• Recent advances on the Hamiltonian problem: survey III
• Some Theorems on Abstract Graphs
• The size Ramsey number of a directed path
• Tight Bounds on Vertex Connectivity Under Sampling
• Tough graphs and Hamiltonian circuits.
• Toughness in graphs -- a survey

Cited in

(12)

• A generalization of Fan's results: Distribution of cycle lengths in graphs
• Distribution of cycle lengths in graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• Variation of Adriatic and Wiener indices for different cycle lengths and paths
• The square of a Hamilton cycle in randomly perturbed graphs
• The power of many colours
• Cycles and trees in randomly perturbed sparse digraphs
• How many random edges make an almost-Dirac graph Hamiltonian?
• Fragile minor-monotone parameters under a random edge perturbation
• Ramsey properties of randomly perturbed hypergraphs
• Minors, connectivity, and diameter in randomly perturbed sparse graphs
• Smoothed analysis of the Komlós conjecture: Rademacher noise

This page was built for publication: Cycle lengths in randomly perturbed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6063344)