𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian cycles and paths in Cayley graphs and digraphs — A survey

✍ Scribed by Stephen J. Curran; Joseph A. Gallian

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
927 KB
Volume
156
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Cayley graphs arise naturally in computer science, in the study of word-hyperbolic groups and automatic groups, in change-ringing, in creating Escher-like repeating patterns in the hyperbolic plane, and in combinatorial designs. Moreover, Babai has shown that all graphs can be realized as an induced subgraph of a Cayley graph of any sufficiently large group.

Since the 1984 survey of results on hamiltonian cycles and paths in Cayley graphs by Witte and Gallian, many advances have been made. In this paper we chronicle these results and include some open problems and conjectures.

📜 SIMILAR VOLUMES

Hamiltonian cycles in cayley color graph
Hamiltonian cycles in cayley color graphs
✍ Joseph B. Klerlein 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 1 views

## Abstract A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph __D__~Δ~(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are

Chvátal-Erdős conditions for pat
Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
✍ Bill Jackson; Oscar Ordaz 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 783 KB

We give a survey of results and conjectures concerning sufficient conditions in terms of connectivity and independence number for which a graph or digraph has various path or cyclic properties, for example hamilton path/cycle, hamilton connected, pancyclic, path/cycle covers, 2-cyclic.

On cycles and paths in digraphs
On cycles and paths in digraphs
✍ M.C. Heydemann 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 273 KB

The purpose of this communication is to announce some slrfficient conditions on degrees and number of arcs to insure the existence of cycles and paths in directed graphs. We show that these results are the best possible. The proofs of the theorems can be found in [4].

Hamiltonian paths and cycles in hypertou
Hamiltonian paths and cycles in hypertournaments
✍ Gutin, Gregory; Yeo, Anders 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V | = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertour

Hamiltonian paths and hamiltonian connec
Hamiltonian paths and hamiltonian connectivity in graphs
✍ Bing Wei 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 388 KB

## Let G be a 2-connected graph with n vertices such that d(u)+d(u)+d(w)-IN(u)nN(u)nN(w)I an+ 1 holds for any triple of independent vertices u, v and w. Then for any distinct vertices u and u such that {u, 0) is not a cut vertex set of G, there is a hamiltonian path between u and o. In particular,