Induced trees in sparse random graphs

DOI10.1007/BF01788097MaRDI QIDQ1086255zbMATH OpenFDO

Authors W. Fernandez de la Vega

Publication date 1986

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01788097

zbMATH Keywords

induced treerandom graph

Mathematics Subject Classification ID

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

Review text

The paper contains the constructive proof of the theorem: If \(c>1\) the random graph G(n,p) on n vertices with edge probability \(p=c/n\) almost surely contains an induced tree on at least \(n\alpha_ c(1-0(1))\) vertices where \(\alpha_ c\) is the positive root of the equation \(c\alpha =\log (1+c^ 2\alpha)\).

Recommendations

• scientific article; zbMATH DE number 932179
• On the order of the largest induced tree in a random graph
• Maximal induces trees in sparse random graphs
• Trees in random graphs
• On large induced trees and long induced paths in sparse random graphs

Cites work

• 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 3693325 (Why is no real title available?)
• scientific article; zbMATH DE number 3726409 (Why is no real title available?)
• Induced trees in sparse random graphs
• Solutions of ordinary differential equations as limits of pure jump markov processes
• The largest tree in a random graph
• The longest path in a random graph
• Trees in random graphs

Cited in

(20)

• Large induced trees in \(K_r\)-free graphs
• 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
• On large induced trees and long induced paths in sparse random graphs
• The size of the largest hole in a random graph
• Large induced trees in sparse random graphs
• scientific article; zbMATH DE number 568829 (Why is no real title available?)
• scientific article; zbMATH DE number 932179 (Why is no real title available?)
• Large induced matchings in random graphs
• On Induced Paths, Holes, and Trees in Random Graphs
• Short proofs for long induced paths
• Induced trees in triangle-free graphs
• The largest hole in sparse random graphs
• The largest hole in sparse random graphs
• Average case analysis of greedy algorithms for optimisation problems on set systems
• Long induced paths in expanders
• The emergence of a giant rainbow component
• Maximum induced trees and forests of bounded degree in random graphs

This page was built for publication: Induced trees in sparse random graphs

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