𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Andrzej Ruciński

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
747 KB
Volume
105
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Rucidski,

A., Matching and covering the vertices of a random graph by copies of a given graph, Discrete Mathematics 105 (1992) 185-197.

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, almost surely, where PM, means that all n vertices can be covered by vertex-disjoint copies of a fixed graph G. For G = K, this is the problem of finding the edge-probability threshold for the existence of a perfect matching solved by ErdGs and RCnyi in 1966. A necessary condition for PM, is the property COV, that each vertex lies in a copy of G. Although for every tree T the thresholds for PM, and COV, coincide (see tuczak and Ruciriski, 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).

📜 SIMILAR VOLUMES

On the number of vertices of given degre
On the number of vertices of given degree in a random graph
✍ Zbigniew Palka 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

This note can be treated a s a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G E ?An, p) asymptotically has a nor

Covering the cliques of a graph with ver
Covering the cliques of a graph with vertices
✍ Paul Erdős; Tibor Gallai; Zsolt Tuza 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 681 KB

The following problem is investigated. Given an undirected graph G, determine the smallest cardinality of a vertex set that meets all complete subgraphs KC G maximal under inclusion.

Covering the vertices of a graph by cycl
Covering the vertices of a graph by cycles of prescribed length
✍ D. Amar; I. Fournier; A. Germa 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

The main theorem of that paper is the following: let G be a graph of order n, of size at least (nZ -3n + 6 ) / 2 . For any integers k, n,, n2,. . . , nk such that n = n, + n2 + ... + nk and n, 2 3, there exists a covering of the vertices of G by disjoint cycles (C,),=,..,k with ICjl = n,, except whe

The number of cut-vertices in a graph of
The number of cut-vertices in a graph of given minimum degree
✍ Michael O. Albertson; David M. Berman 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 228 KB

Albertson, M.O. and D.M. Berman, The number of cut-vertices in a graph of given minimum degree, Discrete Mathematics 89 (1991) 97-100. A graph with n vertices and minimum degree k 2 2 can contain no more than (2k -2)n/(kz -2) cut-vertices. This bound is asymptotically tight. \* Research supported in

On a random graph with immigrating verti
On a random graph with immigrating vertices: Emergence of the giant component
✍ David J. Aldous; Boris Pittel 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB 👁 2 views

A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1/n, is studied. The detailed picture of emergence of giant components with O n 2/3 vertices is shown to be the same as in the Erdős-Rényi graph process with the number of vertices fixed at n at t