✦ LIBER ✦

On the existence of Hamiltonian cycles in a class of random graphs

✍ Scribed by T.I. Fenner; A.M. Frieze

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 468 KB
Volume: 45
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90046-8

No coin nor oath required. For personal study only.

✦ Synopsis

A digraph with n vertices and fixed outdegree m is generated randomly so that each such digraph is equally likely to be chosen. We consider the probability of the existence of a Hamiltonian cycle in the graph obtained by ignoring arc orientation. We show that there exists m (~23) such that a Hamiltonian cycle exists with probability tending to 1 as n tends to infinity.

📜 SIMILAR VOLUMES

Limit distribution for the existence of

Limit distribution for the existence of hamiltonian cycles in a random graph

✍ János Komlós; Endre Szemerédi 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 874 KB

P&a proved that a random graph with clt log n edges is Hamiltonian with probability tending to 1 if c >3. Korsunov improved this by showing that, if Gn is a random graph with \*n log n + in log log n + f(n)n edges and f(n) --\*m, then G" is Hamiltonian, with probability tending to 1. We shall prove

Hamilton Cycles in a Class of Random Dir

Hamilton Cycles in a Class of Random Directed Graphs

✍ C. Cooper; A. Frieze 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 449 KB

On the Approximation of Finding A(nother

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

✍ Cristina Bazgan; Miklos Santha; Zsolt Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 144 KB

It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomial-time algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is given as part of the input. We investigate the co

On Hamiltonian cycles in Cayley graphs o

On Hamiltonian cycles in Cayley graphs of wreath products

✍ Richard Stong 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 314 KB

On the number of hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro

On the number of hamilton cycles in a ra

On the number of hamilton cycles in a random graph

✍ C. Cooper; A. M. Frieze 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 576 KB

Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n)('-')" distinct hamilton cycles for any fixed E > 0.