Adding random edges to dense graphs

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.

14 pages

Cited by in corpus (10)

• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Triangles in randomly perturbed graphs
• Ramsey properties of randomly perturbed dense graphs
• Spanning trees in randomly perturbed graphs
• Rainbow trees in uniformly edge-coloured graphs
• Tree decompositions of graphs without large bipartite holes
• Positional games on randomly perturbed graphs
• A Ramsey-Turán theory for tilings in graphs
• The power of many colours
• The biased odd cycle game