The property of having a k ‐regular subgraph has a sharp threshold |
| |
Authors: | Shoham Letzter |
| |
Institution: | 1. Email:shoham.letzter at mail.huji.ac.il;4. Institute of Mathematics, Hebrew University, Jerusalem, Israel |
| |
Abstract: | In this paper it is proved that in the random graph model G(n,p), the property of containing a k ‐regular subgraph, has a sharp threshold for k ≥ 3. It is also shown how to use similar methods to prove, quite easily, the (known fact of) sharpness of having a non empty k ‐core for k ≥ 3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 509–519, 2013 |
| |
Keywords: | Random graphs regular graphs sharp threshold |
|
|