Embedding nearly-spanning bounded degree trees
From MaRDI portal
(Redirected from Publication:950331)
Abstract: We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed dgeq 2 and 0<epsilon<1, there exists a constant c=c(d,epsilon) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-epsilon)n vertices with maximum degree at most d. We also prove that if an (n,D,lambda)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most lambda in their absolute values) has large enough spectral gap D/lambda as a function of d and epsilon, then G has a copy of every tree T as above.
Recommendations
Cites work
- scientific article; zbMATH DE number 3693325 (Why is no real title available?)
- scientific article; zbMATH DE number 3613090 (Why is no real title available?)
- Expanding graphs contain all small trees
- Hamiltonian circuits in random graphs
- Long paths in sparse random graphs
- On Universal Graphs for Spanning Trees
- On graphs which contain all small trees
- On large matchings and cycles in sparse random graphs
- On the second eigenvalue and random walks in random \(d\)-regular graphs
- Random graphs.
- Sparse pseudo‐random graphs are Hamiltonian
- The longest path in a random graph
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Trees in sparse random graphs
- Universal Graphs for Bounded-Degree Trees and Planar Graphs
Cited in
(35)- Spanning structures and universality in sparse hypergraphs
- Local resilience of almost spanning trees in random graphs
- Expanders Are Universal for the Class of All Spanning Trees
- A randomized embedding algorithm for trees
- Cycle factors and renewal theory
- Fast embedding of spanning trees in biased maker-breaker games
- An improved upper bound on the density of universal random graphs
- Expanding graphs contain all small trees
- The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
- The total acquisition number of random graphs
- The threshold for combs in random graphs
- Tight bounds for embedding bounded degree trees
- Rolling backwards can move you forward: on embedding problems in sparse expanders
- The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
- An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
- Embedding meshes of trees into deBruijn graphs
- Global maker-breaker games on sparse graphs
- Spanning trees in random graphs
- Universality for bounded degree spanning trees in randomly perturbed graphs
- Large bounded degree trees in expanding graphs
- Rainbow trees in uniformly edge‐colored graphs
- Universal and unavoidable graphs
- Universality of random graphs and rainbow embedding
- Optimal threshold for a random graph to be 2-universal
- Degree constrained tree embedding into points in the plane
- Embedding spanning trees in random graphs
- Hamiltonicity in random directed graphs is born resilient
- Embedding graphs with bounded degree in sparse pseudorandom graphs
- Sharp threshold for the appearance of certain spanning trees in random graphs
- Random perturbation of sparse graphs
- Embedding spanning bounded degree subgraphs in randomly perturbed graphs
- Sparse multipartite graphs as partition universal for graphs with bounded degree
- Strong 2-degenerate graph embeddings
- Expanders are universal for the class of all spanning trees
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
This page was built for publication: Embedding nearly-spanning bounded degree trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q950331)
