Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
From MaRDI portal
Abstract: We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is such that if G is an n-vertex graph with minimum degree at least , and T is an n-vertex tree with maximum degree at most , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest.
Recommendations
- Universality for bounded degree spanning trees in randomly perturbed graphs
- Spanning trees in randomly perturbed graphs
- Bounded degree spanning trees (extended abstract)
- scientific article; zbMATH DE number 747032
- Spanning trees in random graphs
- EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
- Tree spanners of bounded degree graphs
- Spanning trees of bounded degree
- Spanning trees with bounded degrees
- Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph
Cites work
- Adding random edges to dense graphs
- Blow-up lemma
- Cycles and matchings in randomly perturbed digraphs and hypergraphs
- Embedding nearly-spanning bounded degree trees
- Embedding spanning trees in random graphs
- Hamiltonian circuits in random graphs
- How many random edges make a dense graph hamiltonian?
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- Large planar subgraphs in dense graphs
- On embedding well-separable graphs
- On smoothed analysis in dense graphs and formulas
- Proof of a Packing Conjecture of Bollobás
- Proof of the bandwidth conjecture of Bollobás and Komlós
- Small subsets inherit sparse \(\varepsilon\)-regularity
- Smoothed analysis of algorithms
- Some Theorems on Abstract Graphs
- Spanning 3-colourable subgraphs of small bandwidth in dense graphs
- Spanning trees in dense graphs
Cited in
(49)- Embedding spanning bounded degree subgraphs in randomly perturbed graphs
- Random perturbation of sparse graphs
- Small rainbow cliques in randomly perturbed dense graphs
- Spanning trees of dense directed graphs
- 2-universality in randomly perturbed graphs
- Isoperimetric numbers of randomly perturbed intersection graphs
- Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
- Vertex Ramsey properties of randomly perturbed graphs
- A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
- The effect of adding randomly weighted edges
- Ramsey properties of randomly perturbed graphs: cliques and cycles
- The genus of the Erdős-Rényi random graph and the fragile genus property
- Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
- Large Rainbow Cliques in Randomly Perturbed Dense Graphs
- EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
- Spanning trees in randomly perturbed graphs
- Tree decompositions of graphs without large bipartite holes
- Powers of tight Hamilton cycles in randomly perturbed hypergraphs
- Universality for bounded degree spanning trees in randomly perturbed graphs
- Tilings in randomly perturbed dense graphs
- Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
- Triangles in randomly perturbed graphs
- Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
- Factors in randomly perturbed hypergraphs
- Rainbow trees in uniformly edge‐colored graphs
- Hamiltonicity of graphs perturbed by a random regular graph
- On powers of tight Hamilton cycles in randomly perturbed hypergraphs
- Hamiltonicity of graphs perturbed by a random geometric graph
- Random growth scale-free networked models with an identical degree distribution and a tunable assortativity index
- A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
- Rainbow cliques in randomly perturbed dense graphs
- Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
- On oriented cycles in randomly perturbed digraphs
- Spanning trees in graphs without large bipartite holes
- 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
- Rainbow subgraphs of uniformly coloured randomly perturbed graphs
- Ramsey properties of randomly perturbed hypergraphs
- Average-case and smoothed analysis of graph isomorphism
- Minors, connectivity, and diameter in randomly perturbed sparse graphs
- Smoothed analysis of the Komlós conjecture: Rademacher noise
- Rainbow connectivity of randomly perturbed graphs
- Rainbow spanning trees in uniformly coloured perturbed graphs (extended abstract)
- Cycles of every length and orientation in randomly perturbed digraphs (extended abstract)
- Hamiltonicity of random subgraphs of the hypercube
- Randomly perturbed digraphs also have bounded-degree spanning trees
- Hamiltonicity in randomly perturbed hypergraphs
- Embedding nearly-spanning bounded degree trees
This page was built for publication: Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957690)
