Long paths in sparse random graphs |
| |
| Authors: | Béla Bollobás |
| |
| Institution: | (1) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, CB2 1SB Cambridge, U.K.;(2) Department of Mathematics, Louisiana State University, 70803 Baton Rouge, LA, USA |
| |
| Abstract: | We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc.
Dedicated to Tibor Gallai on his seventieth birthday |
| |
| Keywords: | 05 C 38 60 C 05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
