On large induced trees and long induced paths in sparse random graphs

DOI10.1016/0095-8956(92)90021-OMaRDI QIDQ1204462zbMATH OpenOpenAlexFDO

Authors W. C. Stephen Suen

Publication date 10 March 1993

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(92)90021-o

zbMATH Keywords

random graphinduced treeinduced path

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 932179
• Induced trees in sparse random graphs
• On the order of the largest induced tree in a random graph
• On induced paths, holes and trees in random graphs
• On Induced Paths, Holes, and Trees in Random Graphs

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• Large holes in sparse random graphs
• Large induced trees in sparse random graphs
• Maximal induces trees in sparse random graphs
• On depth first search trees in \(m\)-out digraphs

Cited in

(15)

• On induced paths, holes and trees in random graphs
• On depth first search trees in \(m\)-out digraphs
• Induced trees in sparse random graphs
• Finding paths in sparse random graphs requires many queries
• Large induced matchings in random graphs
• The largest hole in sparse random graphs
• On Induced Paths, Holes, and Trees in Random Graphs
• Large induced trees in \(K_r\)-free graphs
• Maximal induces trees in sparse random graphs
• MIP formulations for induced graph optimization problems: a tutorial
• Short proofs for long induced paths
• Large induced trees in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random graph
• The largest hole in sparse random graphs
• A parametric analysis of the largest induced tree problem in random graphs

This page was built for publication: On large induced trees and long induced paths in sparse random graphs

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