Journal of Integer Sequences, Vol. 23 (2020), Article 20.7.6

Orbits of Hamiltonian Paths and Cycles in Complete Graphs

Samuel Herman and Eirini Poimenidou
Division of Natural Sciences
New College of Florida
Sarasota, FL 34243


We enumerate certain geometric equivalence classes of subgraphs induced by Hamiltonian paths and cycles in complete graphs. These classes are orbits under the action of certain direct products of dihedral and cyclic groups on sets of strings representing subgraphs. The orbits are enumerated using Burnside's lemma. The technique used also provides an alternative proof of the formulae found by Golomb and Welch, which give the number of distinct n-gons on fixed, regularly spaced vertices up to rotation and optionally reflection.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000939 A000940 A089066 A099030 A275527.)

Received May 17 2019; revised versions received January 8 2020; March 28 2020. Published in Journal of Integer Sequences, June 27 2020.

Return to Journal of Integer Sequences home page