Trees in sparse random graphs

DOI10.1016/0095-8956(88)90056-1MaRDI QIDQ1113925zbMATH OpenOpenAlexFDO

Authors W. Fernandez de la Vega

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(88)90056-1

zbMATH Keywords

random graph evolutionsparse Bernoulli graphstrees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Review text

It is shown that large trees with restricted degrees are contained in sparse Bernoulli graphs with arbitrarily high probability as the order of the graph tends to infinity.

Cites work

• scientific article; zbMATH DE number 3916307 (Why is no real title available?)
• scientific article; zbMATH DE number 3693325 (Why is no real title available?)
• The longest path in a random graph

Cited in

(14)

• The block connectivity of random trees
• Maximal induces trees in sparse random graphs
• Large induced trees in sparse random graphs
• Tree components in random distance graphs of special form
• Spanning trees in random series-parallel graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• Grids in random graphs
• scientific article; zbMATH DE number 6123974 (Why is no real title available?)
• Expanders Are Universal for the Class of All Spanning Trees
• A randomized embedding algorithm for trees
• Expanders are universal for the class of all spanning trees
• Rainbow trees in uniformly edge‐colored graphs
• Embedding nearly-spanning bounded degree trees

This page was built for publication: Trees in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113925)