|
|||||
|
|
One-factor in random graphs based on vertex choice |
|
| Authors: | E. Shamir E. Upfal |
| Affiliation: | Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel;Institute of Mathematics, The Hebrew University, Jerusalem, Israel |
| Abstract: | The following result is proved: Consider a random graph on n vertices where each vertex chooses randomly a set of c neighbors. If c?6, then the graph has a 1-factor, with probability→1 as n→∞. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |