|
|||||
|
|
On the threshold for k-regular subgraphs of random graphs |
|
| Authors: | Pawe? Pra?at Jacques Verstra?te Nicholas Wormald |
| Institution: | 1. Department of Mathematics, Ryerson University, Toronto, ON, Canada 2. Department of Mathematics, University of California, San Diego, CA, USA 3. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada |
| Abstract: | The k-core of a graph is the largest subgraph of minimum degree at least k. We show that for k sufficiently large, the threshold for the appearance of a k-regular subgraph in the Erdős-Rényi random graph model G(n,p) is at most the threshold for the appearance of a nonempty (k+2)-core. In particular, this pins down the point of appearance of a k-regular subgraph to a window for p of width roughly 2/n for large n and moderately large k. The result is proved by using Tutte’s necessary and sufficient condition for a graph to have a k-factor. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |