𝔖 Bobbio Scriptorium
✦   LIBER   ✦

First cycles in random directed graph processes

✍ Scribed by Béla Bollobás; Steen Rasmussen

Book ID
103059490
Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
749 KB
Volume
75
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Long cycles in subgraphs of (pseudo)rand
Long cycles in subgraphs of (pseudo)random directed graphs
✍ Ido Ben-Eliezer; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant __c__ = __c__(γ) such that the following holds. Let __G__ = (__V, E__) be a (pseudo)random directed graph on __n__ vertice

Cycles in random graphs
Cycles in random graphs
✍ Tomasz Łuczak 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 348 KB

tuczak, T., Cycles in random graphs, Discrete Mathematics 98 (1991) 231-236. Let G(n, p) be a graph on n vertices in which each possible edge is presented independently with probability p = p(n) and u'(n, p) denote the number of vertices of degree 1 in G(n, p). It is shown that if E > 0 and rip(n)))

Disjoint Hamilton cycles in the random g
Disjoint Hamilton cycles in the random geometric graph
✍ Tobias Müller,; Xavier Pérez-Giménez;; Nicholas Wormald 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 270 KB

We consider the standard random geometric graph process in which n vertices are placed at random on the unit square and edges are sequentially added in increasing order of edge-length. For fixed k ≥ 1, we prove that the first edge in the process that creates a k-connected graph coincides a.a.s. with