Hamiltonian Paths in Gear Graphs: A Simple Quadratic Conjecture

Abstract

We study Hamiltonian paths in the gear graph G_n , which consists of a cycle of n rim” vertices with inserted vertices between successive rims and a central vertex connected to each rim. For n=3,…,7 we compute the number of Hamiltonian paths. he resulting sequence of counts (up to reversal) is 12,20,30,42, 56, . . . ., which fits the quadratic formula n (n + 1). We conjecture that the number of Hamiltonian paths in G_n up to reversal is exactly n (n + 1) for all n ≥3.