## Matching and covering the vertices of a random graph by copies of a given graph

### Authors:

- Andrzej Ruciński

### Abstract

In this paper we partially answer the question: how slowly must p(n) converge to 0 so that a random graph K(n, p) has property PM_{G} almost surely, where PM_{G} means that all n vertices can be covered by vertex-disjoint copies of a fixed graph G. For G = K_{2} this is the problem of finding the edge-probability threshold for the existence of a perfect matching solved by Erdős and Rényi in 1966. A necessary condition for PM_{G} is the property COV_{G} that each vertex lies in a copy of G. Although for every tree T the thresholds for PM_{T} and COV_{G} coincide (see Łuczak and Ruciński, 1990) it is not the case for general G and a class of counterexamples will be presented. We also establish a threshold theorem for matching all but o(n) vertices into vertex-disjoint copies of G. Most proofs make use of a recent correlation inequality from Janson et al. (1990). © 1992.

- Record ID
- UAMdf8af5d3e3cc43a983ea1228bb1193f2
- Author
- Journal series
- Discrete Mathematics, ISSN 0012-365X
- Issue year
- 1992
- Vol
- 105
- Pages
- 185-197
- ASJC Classification
- ;
- DOI
- DOI:10.1016/0012-365X(92)90141-2 opening in a new tab
- Language
- en English
- Score (nominal)
- 20
- Score source
- journalList
- Publication indicators
- = 16.000; : 1999 = 0.846; : 2006 = 0.347 (2) - 2007=0.501 (5)

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAMdf8af5d3e3cc43a983ea1228bb1193f2/

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perishopening in a new tab system.

Back