On factors in random graphs |
| |
| Authors: | E Shamir E Upfal |
| |
| Institution: | (1) Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, Israel;(2) Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel |
| |
| Abstract: | The following result is proved: LetG
n,p be a random graph withn vertices and probabilityp for an edge. Ifp is such that the random graph has min-degree at leastr with probability 1, then anyf-factor 1≦f≦r exists with probability 1, asn→∞. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
