|
|||||
|
|
Induced trees in sparse random graphs |
|
| Authors: | W Fernandez de la Vega |
| Institution: | (1) Laboratoire de Recherche en Informatique, Université de Paris-Sud, Centre d'Orsay, Bât. 490, 91405 Orsay Cedex, France |
| Abstract: | The random graphG(n, p) onn vertices with edge probabilityp = c/n contains an induced tree of order
c
n where
c
> 0 forc > 1. This proves a conjecture of Erdös and Palka. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |