Journal of Graph Theory · 2014 · 14 citations · 6 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsProbability TheoryDirected Acyclic GraphsGraph AlgorithmsGraph TheoryProbabilistic CombinatoricsRandom Graph ModelsRandom Graph TheoryRandom GraphsRandomized Graph AlgorithmsThreshold Functions
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.
6