✦ LIBER ✦

On large matchings and cycles in sparse random graphs

✍ Scribed by A.M Frieze

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 666 KB
Volume: 59
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90171-8

No coin nor oath required. For personal study only.

✦ Synopsis

Let k be a fixed positive integer. A graph H has property Mk if it contains [½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induced subgraph Ilk with property Mk and such that IV(Hk)I = (1 --(1 + e(c))ck-Xe-C/ (k -1)!)n, where e(c)--~O as c--~ oo. In particular this shows that for large c, G,,p a.s. contains a matching of size ½(1 -(1 + e(c))e-C)n (k = 1) and a cycle of size (1 -(1 + e(c))ce-C)n (k = 2).

📜 SIMILAR VOLUMES

Maximum matchings in sparse random graph

Maximum matchings in sparse random graphs: Karp–Sipser revisited

✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 490 KB 👁 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3

Random Matchings Which Induce Hamilton C

Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs

✍ Jeong Han Kim; Nicholas C. Wormald 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 215 KB

Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set

On-Line Coloring of Sparse Random Graphs

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr

Hamilton cycles in random graphs and dir

Hamilton cycles in random graphs and directed graphs

✍ Colin Cooper; Alan Frieze 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 3 views

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

Large induced forests in sparse graphs

✍ Noga Alon; Dhruv Mubayi; Robin Thomas 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB

## Abstract For a graph __G__, let __a__(__G__) denote the maximum size of a subset of vertices that induces a forest. Suppose that __G__ is connected with __n__ vertices, __e__ edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and __G__ ≠ __K__~4~, then __a__(__G__) ≥ __n__ − e/4 − 1