On large induced trees and long induced paths in sparse random graphs
type: Item
instance of: scholarly article
title: On large induced trees and long induced paths in sparse random graphs
zbMATH Open document ID: 0779.05052
DOI: 10.1016/0095-8956(92)90021-O
author: W. C. Stephen Suen
published in: Journal of Combinatorial Theory. Series B
publication date: 1993-03-10T00:00:00Z
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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 130558
zbMATH Keywords: induced tree
zbMATH Keywords: random graph
zbMATH Keywords: induced path
MaRDI profile type: Publication
cites work: Q3682518
cites work: Large induced trees in sparse random graphs
cites work: Large holes in sparse random graphs
cites work: Maximal induces trees in sparse random graphs
cites work: On depth first search trees in \(m\)-out digraphs
full work available at URL: 0095-8956(92)90021-o
OpenAlex ID: W2040697623
description: scientific article; zbMATH DE number 130558