## Abstract

Let H be a graph on h vertices, and G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n/h vertex disjoint copies of H. The fractional arboricity of H is [formula omitted], where the maximum is taken over all subgraphs (V′, E′) of H with |V′| > 1. Let δ(H) denote the minimum degree of a vertex of H. It is shown that if δ(H) < a(H), then n^{−1/a(H}) is a sharp threshold function for the property that the random graph G(n, p) contains an H-factor. That is, there are two positive constants c and C so that for p(n) = cn^{−1/a(H}) almost surely G(n, p(n)) does not have an H-factor, whereas for p(n) = Cn^{−1/a(H}), almost surely G(n, p(n)) contains an H-factor (provided h divides n). A special case of this answers a problem of Erdős.

Original language | English (US) |
---|---|

Pages (from-to) | 137-144 |

Number of pages | 8 |

Journal | Combinatorics, Probability and Computing |

Volume | 2 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1993 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics