2-generated Cayley digraphs on nilpotent groups have hamiltonian paths

2011/03/28 by Dave Witte Morris, Morris, Dave Witte
Computer Science · Engineering · Mathematics · #05C20 #05C25 #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems #math.CO #msc:05C20 #msc:05C25 #msc:05C45

paper · pdf · doi:10.48550/arxiv.1103.5293

7 pages, no figures; corrected a few typographical errors

openalex publication_date 2011/03/28 · arxiv created 2011/06/30 · arxiv updated 2011/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Suppose G is a nilpotent, finite group. We show that if a,b is any 2-element generating set of G, then the corresponding Cayley digraph Cay(G;a,b) has a hamiltonian path. This implies there is a hamiltonian path in every connected Cayley graph on G that has valence at most 4.

Related

• On Cayley digraphs that do not have hamiltonian paths
• Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)
• Cayley graphs of order 27p are hamiltonian
• Cayley graphs of order 30p are hamiltonian
• Cayley graphs of order 6pq are Hamiltonian