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

induced pathinduced treerandom graph

Mathematics Subject Classification ID

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

Review text

By analyzing an algorithm for finding the induced trees in a graph, probabilistic bounds are obtained on the order of the largest induced tree in a sparse random graph. Similar results on the length of the longest induced path are obtained by considering the path joining the root of an induced tree to a leaf.

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

(18)

• Large induced trees in \(K_r\)-free graphs
• Induced trees in sparse random graphs
• Maximal induces trees in sparse random graphs
• Large induced trees in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random graph
• Finding paths in sparse random graphs requires many queries
• A parametric analysis of the largest induced tree problem in random graphs
• scientific article; zbMATH DE number 932179 (Why is no real title available?)
• On induced paths, holes and trees in random graphs
• 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
• MIP formulations for induced graph optimization problems: a tutorial
• The largest hole in sparse random graphs
• On depth first search trees in \(m\)-out digraphs
• Long induced paths in expanders
• The emergence of a giant rainbow component

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)