Embedding nearly-spanning bounded degree trees

DOI10.1007/S00493-007-2182-ZzbMATH Open1164.05032arXiv0706.4100OpenAlexW2069505580WikidataQ105583422 ScholiaQ105583422MaRDI QIDQ950331FDOQ950331

Benny Sudakov, Noga Alon, Michael Krivelevich

Publication date: 22 October 2008

Published in: Combinatorica (Search for Journal in Brave)

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.

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

zbMATH Keywords

spanning treesembedding

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Sparse pseudo‐random graphs are Hamiltonian
• Trees in sparse random graphs
• Expanding graphs contain all small trees
• Random graphs.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Hamiltonian circuits in random graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• On Universal Graphs for Spanning Trees
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• The longest path in a random graph
• Long paths in sparse random graphs
• On graphs which contain all small trees
• On large matchings and cycles in sparse random graphs

Cited In (29)

• The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition
• Almost spanning subgraphs of random graphs after adversarial edge removal
• 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
• An improved upper bound on the density of universal random graphs
• Fast embedding of spanning trees in biased maker-breaker games
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• The threshold for combs in random graphs
• The total acquisition number of random graphs
• Embedding meshes of trees into deBruijn graphs
• Cycle Factors and Renewal Theory
• Spanning trees in random graphs
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Global maker-breaker games on sparse graphs
• Title not available (Why is that?)
• Rainbow trees in uniformly edge‐colored graphs
• Universal and unavoidable graphs
• Optimal threshold for a random graph to be 2-universal
• Universality of random graphs and rainbow embedding
• Degree constrained tree embedding into points in the plane
• Hamiltonicity in random directed graphs is born resilient
• 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
• Rolling backwards can move you forward: On embedding problems in sparse expanders
• 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)