Adding random edges to dense graphs

DOI10.1002/rsa.10112zbMath1034.05042arXiv1605.07237WikidataQ57401511 ScholiaQ57401511MaRDI QIDQ4459584

Michael Krivelevich, Tom Bohman, Ryan R. Martin, Alan M. 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

05C80: Random graphs (graph-theoretic aspects)

05C12: Distance in graphs

05C40: Connectivity

Related Items

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, Expansion and Lack Thereof in Randomly Perturbed Graphs, Triangles 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, Cycles and matchings in randomly perturbed digraphs and hypergraphs, 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, Vertex Ramsey properties of randomly perturbed graphs

Cites Work

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