Trees in random graphs

DOI10.1016/0012-365X(83)90247-9MaRDI QIDQ790843zbMATH OpenOpenAlexFDO

Authors Zbigniew Palka, P. Erdős

Publication date 1983

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(83)90247-9

zbMATH Keywords

induced starmaximal induced tree

Mathematics Subject Classification ID

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

Review text

The probability space consisting of all graphs on a set of \(n\) vertices where each edge occurs with probability \(p\), independently of all other edges, is denoted by \(G(n,p)\). Theorem: For each \(\epsilon>0\) almost every graph \(G\in G(n,p)\) is such if \((1+\epsilon)\log n/\log d<r<(2- \epsilon)\log n/\log d\) where \(d=1/(1-p),\) then \(G\) contains a maximal induced tree of order \(d\). Problem: Let \(p\) be a function of \(n\), find such a value of \(p\) for which a graph \(G\in G(n,p)\) has the greatest induced tree.

Recommendations

• On the order of the largest induced tree in a random graph
• Publication:4726290
• Maximal induces trees in sparse random graphs
• scientific article; zbMATH DE number 3920488
• scientific article; zbMATH DE number 932179

Cites work

• Cliques in random graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3683612 (Why is no real title available?)
• scientific article; zbMATH DE number 3726409 (Why is no real title available?)
• Topological cliques of random graphs

Cited in

(27)

• Large induced trees in \(K_r\)-free graphs
• The block connectivity of random trees
• Induced trees in sparse random graphs
• On the order of the largest induced tree in a random graph
• Large holes in sparse random graphs
• Maximal induces trees in sparse random graphs
• The size of the largest hole in a random graph
• Large induced trees in sparse random graphs
• Tree components in random distance graphs of special form
• Maximum induced forests in random graphs
• Dominating and large induced trees in regular graphs
• On the sizes of large subgraphs of the binomial random graph
• scientific article; zbMATH DE number 3920488 (Why is no real title available?)
• A parametric analysis of the largest induced tree problem in random graphs
• Random Trees in Random Graphs
• On random cartesian trees
• scientific article; zbMATH DE number 3999982 (Why is no real title available?)
• scientific article; zbMATH DE number 6123974 (Why is no real title available?)
• Nodes of large degree in random trees and forests
• Large induced matchings in random graphs
• On Induced Paths, Holes, and Trees in Random Graphs
• Short proofs for long induced paths
• The largest hole in sparse random graphs
• The largest hole in sparse random graphs
• Maximum induced subgraphs of the binomial random graph
• Long induced paths in expanders
• Maximum induced trees and forests of bounded degree in random graphs

This page was built for publication: Trees in random graphs

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