Adding random edges to dense graphs

DOI10.1002/RSA.10112MaRDI QIDQ4459584zbMATH OpenOpenAlexWikidataFDO

Authors Tom Bohman, Michael Krivelevich, Ryan R. Martin, Alan Frieze

Publication date 29 March 2004

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

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

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Abstract: This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone properties including the appearance of a fixed size clique, small diameter and $k$-connectivity.

Recommendations

• The effect of adding randomly weighted edges
• How many random edges make a dense graph hamiltonian?
• Connectivity of random addable graphs
• How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?
• scientific article; zbMATH DE number 3904630

Cites work

• Combinatorics, Paul Erdős is eighty. Vol. 1

Cited in

(29)

• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Highly connected subgraphs of graphs with given independence number
• The biased odd cycle game
• Small rainbow cliques in randomly perturbed dense graphs
• 2-universality in randomly perturbed graphs
• Isoperimetric numbers of randomly perturbed intersection graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Vertex Ramsey properties of randomly perturbed graphs
• The effect of adding randomly weighted edges
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Maker-Breaker games on randomly perturbed graphs
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Tree decompositions of graphs without large bipartite holes
• Tilings in randomly perturbed dense graphs
• Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Triangles in randomly perturbed graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Cycle lengths in randomly perturbed graphs
• Rainbow trees in uniformly edge‐colored graphs
• A Ramsey–Turán theory for tilings in graphs
• The power of many colours
• How many random edges make an almost-Dirac graph Hamiltonian?
• Minors, connectivity, and diameter in randomly perturbed sparse graphs
• Smoothed analysis of the Komlós conjecture: Rademacher noise
• Rainbow connectivity of randomly perturbed graphs

This page was built for publication: Adding random edges to dense graphs

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