On vertex-transitive graphs with a unique hamiltonian cycle

2023/03/20 by Babak Miraftab, Dave Witte Morris, Miraftab, Babak +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Geometric and Algebraic Topology

paper · pdf · doi:10.48550/arxiv.2303.11124

openalex publication_date 2023/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph is said to be uniquely hamiltonian if it has a unique hamiltonian cycle. For a natural extension of this concept to infinite graphs, we find all uniquely hamiltonian vertex-transitive graphs with finitely many ends, and also discuss some examples with infinitely many ends. In particular, we show each nonabelian free group F_n has a Cayley graph of degree 2n + 2 that has a unique hamiltonian circle. (A weaker statement had been conjectured by A. Georgakopoulos.) Furthermore, we prove that these Cayley graphs of F_n are outerplanar.

Related

• Symmetry classes of Hamiltonian cycles
• Vertex-transitive graphs that have no Hamilton decomposition
• Infinitely many nonsolvable groups whose Cayley graphs are hamiltonian
• On hamiltonian cycles in Cayley graphs of order pqrs
• Cayley graphs of order 8pq are hamiltonian