TOPICS
Search

Uniquely Hamiltonian Graph

A uniquely Hamiltonian graph is a graph possessing a single Hamiltonian cycle.

Classes of uniquely Hamiltonian graphs include the cycle graphs C_n, Hanoi graphs H_n, ladder graphs P_2 square P_n (for n>1), middle layer graphs H(2n+1,n), sun graphs, and uniquely pancyclic graphs.

UniquelyHamiltonianGraphs

The numbers of uniquely Hamiltonian graphs on n=1, 2, ... are 0, 0, 1, 2, 3, 12, 49, 482, 6380, ... (OEIS A307956) and the corresponding numbers of planar uniquely Hamiltonian graphs are 0, 0, 1, 2, 3, 12, 49, 460, 4994, ... (OEIS A307957).

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

See also

Hamiltonian Cycle, Hamiltonian Graph, Uniquely Pancyclic Graph

Explore with Wolfram|Alpha

References

Goedgebeura, J.; Meersman, B.; Zamfirescu, C. T. "Graphs with few Hamiltonian Cycles." 15 Jul 2019. https://arxiv.org/abs/1812.05650.Sloane, N. J. A. Sequences A307956 and A307957 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Uniquely Hamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UniquelyHamiltonianGraph.html

Subject classifications