Uniquely Hamiltonian Graph

A uniquely Hamiltonian graph is a graph possessing a single Hamiltonian cycle. The enumerations and results below concern finite undirected simple graphs.

Classes of uniquely Hamiltonian graphs include the cycle graphs , Hanoi graphs , ladder graphs (for ), complete sun graphs, and uniquely pancyclic graphs with at least three vertices.

The numbers of uniquely Hamiltonian graphs on , 2, ... are 0, 0, 1, 2, 3, 12, 49, 482, 6380, ... (OEIS A307956; Goedgebeur et al. 2019, Table 4) and the corresponding numbers of planar uniquely Hamiltonian graphs are 0, 0, 1, 2, 3, 12, 49, 460, 4994, ... (OEIS A307957; Goedgebeur et al. 2019, Table 1).

A Hamiltonian cubic graph contains at least three Hamiltonian cycles, so there are no uniquely Hamiltonian cubic graphs (Goedgebeur et al. 2019).

Fleischner (2014) constructed uniquely Hamiltonian graphs in which every vertex has vertex degree 4 or 14. His smallest examples with vertex connectivity 2 and 3 have 338 and 408 vertices, respectively (Fleischner 2014, Goedgebeur et al. 2019). In this work, graphs related to this construction are known as Fleischner graphs.

Barefoot and Entringer (1981) proved that for every , there exist exactly uniquely Hamiltonian graphs of maximum edge count (Goedgebeur et al. 2019), where is the ceiling function.

There are no -regular uniquely Hamiltonian graphs for (Haxell et al. 2007, Fleischner 2014, Brinkmann and De Pauw 2024).