Large induced trees in sparse random graphs

DOI10.1016/0095-8956(87)90039-6zbMath0617.05056OpenAlexW2017075410WikidataQ57401624 ScholiaQ57401624MaRDI QIDQ1821799

Alan M. Frieze, Bill Jackson

Publication date: 1987

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(87)90039-6

zbMATH Keywords

random regular graphsRandom graphsinduced treesrandom regular digraphs

Mathematics Subject Classification ID

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

Related Items (11)

On Induced Paths, Holes, and Trees in Random Graphs ⋮ Short proofs for long induced paths ⋮ On tree census and the giant component in sparse random graphs ⋮ Large holes in sparse random graphs ⋮ Maximal induces trees in sparse random graphs ⋮ The largest hole in sparse random graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ 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 \(K_r\)-free graphs ⋮ Large Induced Matchings in Random Graphs

Cites Work

• Long paths in sparse random graphs
• Trees in random graphs
• The largest tree in a random graph
• On the order of the largest induced tree in a random graph
• Large holes in sparse random graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Unnamed Item
• Unnamed Item

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