Paperlane

no. 13 · Wednesday 11 November 2026

Hamilton cycles in vertex-transitive graphs of prime-power order

Farzad Maghsoudi, Dragan Marušič and Bobby Miraftab

math.CO

Abstract

A graph is vertex-transitive if, for any two vertices, there is an automorphism mapping one to the other. We prove that every connected vertex-transitive graph of order $p^n$, where $p$ is a prime and $p^n\geq 3$, has a hamiltonian cycle. Our main tool extends Witte's theorem [JCTB (1986)] on Cayley digraphs of $p$-groups.

fields
Combinatorics
pdf ↗ page arXiv:2611.13415 ↗