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
USA
Abstract:
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