Embedding nearly-spanning bounded degree trees
From MaRDI portal
Publication:950331
DOI10.1007/s00493-007-2182-zzbMath1164.05032arXiv0706.4100OpenAlexW2069505580WikidataQ105583422 ScholiaQ105583422MaRDI QIDQ950331
Noga Alon, Michael Krivelevich, Benjamin Sudakov
Publication date: 22 October 2008
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0706.4100
Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)
Related Items
Universal and unavoidable graphs, The total acquisition number of random graphs, Rolling backwards can move you forward: On embedding problems in sparse expanders, Global maker-breaker games on sparse graphs, Spanning structures and universality in sparse hypergraphs, Rainbow trees in uniformly edge‐colored graphs, Embedding spanning bounded degree subgraphs in randomly perturbed graphs, Bounded-Degree Spanning Trees in Randomly Perturbed Graphs, Cycle Factors and Renewal Theory, Fast embedding of spanning trees in biased maker-breaker games, Sparse multipartite graphs as partition universal for graphs with bounded degree, Expanders Are Universal for the Class of All Spanning Trees, The threshold for combs in random graphs, A randomized embedding algorithm for trees, Random perturbation of sparse graphs, Local resilience of almost spanning trees in random graphs, Universality of random graphs and rainbow embedding, Universality for bounded degree spanning trees in randomly perturbed graphs, An improved upper bound on the density of universal random graphs, Optimal threshold for a random graph to be 2-universal, Almost spanning subgraphs of random graphs after adversarial edge removal, Hamiltonicity in random directed graphs is born resilient, Spanning trees in random graphs, Unnamed Item, The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition, Sharp threshold for the appearance of certain spanning trees in random graphs
Cites Work
- Long paths in sparse random graphs
- Expanding graphs contain all small trees
- On large matchings and cycles in sparse random graphs
- Trees in sparse random graphs
- The longest path in a random graph
- On the second eigenvalue and random walks in random \(d\)-regular graphs
- Hamiltonian circuits in random graphs
- On graphs which contain all small trees
- Universal Graphs for Bounded-Degree Trees and Planar Graphs
- On Universal Graphs for Spanning Trees
- Sparse pseudo‐random graphs are Hamiltonian
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
