Universality for bounded degree spanning trees in randomly perturbed graphs

DOI10.1002/rsa.20850zbMath1433.05275arXiv1802.04707OpenAlexW2962757025WikidataQ128085905 ScholiaQ128085905MaRDI QIDQ5216180

Julia Böttcher, Yoshiharu Kohayakawa, Richard Montgomery, Yury Person, Jie Han, Olaf Parczyk

Publication date: 14 February 2020

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

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

zbMATH Keywords

random graphsuniversalityspanning treesperturbed graphs

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Related Items (21)

Large Rainbow Cliques in Randomly Perturbed Dense Graphs ⋮ 2-universality 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 ⋮ Speeding up random walk mixing by starting from a uniform vertex ⋮ A Ramsey–Turán theory for tilings in graphs ⋮ Dirac-type conditions for spanning bounded-degree hypertrees ⋮ Tree decompositions of graphs without large bipartite holes ⋮ Random perturbation of sparse graphs ⋮ Powers of tight Hamilton cycles in randomly perturbed hypergraphs ⋮ Tilings in Randomly Perturbed Dense Graphs ⋮ Vertex Ramsey properties of randomly perturbed graphs ⋮ Small rainbow cliques in randomly perturbed dense graphs ⋮ Ramsey properties of randomly perturbed graphs: cliques and cycles ⋮ Hamiltonicity in randomly perturbed hypergraphs ⋮ Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers ⋮ Rainbow Hamilton Cycles in Randomly Colored Randomly Perturbed Dense Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Embedding nearly-spanning bounded degree trees
• Threshold functions
• Hamiltonian circuits in random graphs
• Hamilton \(\ell\)-cycles in randomly perturbed hypergraphs
• Large bounded degree trees in expanding graphs
• Tree embeddings
• Spanning Trees in Dense Graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• How many random edges make a dense graph hamiltonian?
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs
• Some Theorems on Abstract Graphs

This page was built for publication: Universality for bounded degree spanning trees in randomly perturbed graphs