✦ LIBER ✦

Sparse pseudo-random graphs are Hamiltonian

✍ Scribed by Michael Krivelevich; Benny Sudakov

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 133 KB
Volume: 42
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10065

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies

and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log^5^ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003

📜 SIMILAR VOLUMES

Bisecting sparse random graphs

✍ Malwina J. Luczak; Colin McDiarmid 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB 👁 1 views

Hamiltonian groups are color-graph-hamil

Hamiltonian groups are color-graph-hamiltonian

✍ Joseph B. Klerlein; A. Gregory Starling 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 171 KB

## Abstract A group Γ is said to be color ‐graph ‐hamiltonian if Γ has a minimal generating set Δ such that the Cayley color graph __D__~Δ~(Γ) is hamiltonian. It is shown that every hamiltonian group is color ‐graph ‐hamiltonian.

The Diameter of Sparse Random Graphs

✍ Fan Chung; Linyuan Lu 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 150 KB

We consider the diameter of a random graph G n p for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of rand

Independent sets in random sparse graphs

✍ Pedro G. Gazmuri 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

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

Tough enough chordal graphs are Hamilton

Tough enough chordal graphs are Hamiltonian

✍ Chen, Guantao; Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 3 views

We prove that every 18-tough chordal graph has a Hamiltonian cycle.