|
|||||
|
|
How many random edges make a graph hamiltonian? |
|
| Authors: | Eli Shamir |
| Institution: | (1) Mathematics Institute, The Hebrew University, Jerusalem, Israel |
| Abstract: | A threshold for a graph propertyQ in the scale of random graph spacesG n,p is ap-band across which the asymptotic probability ofQ jumps from 0 to 1. We locate a sharp threshold for the property of having a hamiltonian path. |
| Keywords: | 60 C 05 |
| 本文献已被 SpringerLink 等数据库收录！ | |