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 the normal view instead:
scientific article; zbMATH DE number 3983224
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8788484334945679
0 references
0.8723173141479492
0 references
0.8537962436676025
0 references
0.8488979339599609
0 references
