Nonvertex‐Balanced Factors in Random Graphs |
| |
| Authors: | Stefanie Gerke Andrew McDowell |
| |
| Affiliation: | MATHEMATICS DEPARTMENT, ROYAL HOLLOWAY COLLEGE, UNIVERSITY OF LONDON, EGHAM, ENGLAND |
| |
| Abstract: | We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an H‐factor in a random graph  . We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model. |
| |
| Keywords: | random graphs factors digraphs |
|
|
