Induced trees in sparse random graphs (Q1086255)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Induced trees in sparse random graphs |
scientific article; zbMATH DE number 3983224
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Induced trees in sparse random graphs |
scientific article; zbMATH DE number 3983224 |
Statements
Induced trees in sparse random graphs (English)
0 references
1986
0 references
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)\).
0 references
random graph
0 references
induced tree
0 references
