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), 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; 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 degree 4 or 14. His smallest examples with 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 n>=7, there exist exactly 2^([n/2]-4) uniquely hamiltonian graphs of maximum size (Goedgebeur et al. 2019).

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

See also

Fleischner Graphs, Hamiltonian Cycle, Hamiltonian Graph, Uniquely Pancyclic Graph

Explore with Wolfram|Alpha

References

Barefoot, C. A. and Entringer, R. C. "A Census of Maximum Uniquely Hamiltonian Graphs." J. Graph Th. 5, 315-321, 1981.Bondy, J. A. and Jackson, B. "Vertices of Small Degree in Uniquely Hamiltonian Graphs." J. Combin. Th., Ser. B 74, 265-275, 1998.Brinkmann, G. and De Pauw, M. "Uniquely Hamiltonian Graphs for Many Sets of Degrees." Disc. Math. Comput. Sci. 26, No. 3, #7, 2024. https://arxiv.org/pdf/2304.08946.Fleischner, H. "Uniquely Hamiltonian Graphs of Minimum Degree 4." J. Graph Th. 75, 167-177, 2014.Goedgebeur, J.; Meersman, B.; and Zamfirescu, C. T. "Graphs with Few Hamiltonian Cycles." 15 Jul 2019. https://arxiv.org/abs/1812.05650.Haxell, P.; Seamone, D.; and Verstraete,J. " Independent Dominating Sets and Hamiltonian Cycles." J. Graph Th. 54, 233-234, 2007.Sloane, N. J. A. Sequences A307956 and A307957 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Uniquely Hamiltonian Graph

Cite this as:

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

Subject classifications