✦ LIBER ✦

Hamilton Cycles in a Class of Random Directed Graphs

✍ Scribed by C. Cooper; A. Frieze

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 449 KB
Volume: 62
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1060

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

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

Generating and Counting Hamilton Cycles

Generating and Counting Hamilton Cycles in Random Regular Graphs

✍ Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 216 KB

Let G be chosen uniformly at random from the set G G r, n of r-regular graphs w x Ž . with vertex set n . We describe polynomial time algorithms that whp i find a Ž . Hamilton cycle in G, and ii approximately count the number of Hamilton cycles in G.

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

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

Hamilton cycles in strong products of gr

Hamilton cycles in strong products of graphs

✍ Daniel Král'; Jana Maxová; Robert Šámal; Pavel Podbrdský 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB

## Abstract We prove that the strong product of any __n__ connected graphs of maximum degree at most __n__ contains a Hamilton cycle. In particular, __G__^Δ(__G__)^ is hamiltonian for each connected graph __G__, which answers in affirmative a conjecture of Bermond, Germa, and Heydemann. © 2005 Wile