logo

Uniquely hamiltonian graphs

A uniquely hamiltonian graph is a graph which contains exactly one hamiltonian cycle.

The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip. All results were obtained with the program GenerateUHG (see [1]).

Uniquely hamiltonian graphs
Verticesgirth ≥ 3girth ≥ 4girth ≥ 5
3100
4210
5311
61221
74931
8482113
96380384
1013525225010
113939509217132
1216680047025518167
139739584172388854899
1481871731236472831106470
159535322610327617135562155815
16?4915591680549981
17?1742038139676155795
18?752632929953178520177
19??1123544810
20??18005054988
21??322434738089
22??6427598615569
Go to top

Planar uniquely hamiltonian graphs
Verticesgirth ≥ 3girth ≥ 4girth ≥ 5
3100
4210
5311
61221
74931
8460113
94994334
10682341788
11997486101123
1215582567681691
1325300552147669317
1442506803763529011353
157329357286926805126473
1612936387241772093943330834
17?166713951148907
18?1352143860768178
19?111299229823987517
20??20767030
21??110819167
22??599311836
23??3256610004
Go to top

Nearly cubic uniquely hamiltonian graphs

The following table contains the counts of nearly cubic uniquely hamiltonian graphs. A graph is nearly cubic if it contains exactly two vertices of degree 4 and all other vertices have degree 3. (Note that nearly cubic graphs must have even order).

VerticesNearly cubic UHG's
0-160
181
2020
22337
244592
Go to top

Uniquely hamiltonian graphs of minimum degree 3

It was shown by Royle [2] that the smallest uniquely hamiltonian graphs with minimum degree at least 3 have 18 vertices. The following table contains the counts of all uniquely hamiltonian graphs with girth at least 5 and minimum degree at least 3 up to 22 vertices. All of these graphs have girth 5 and minimum degree 3. Furthermore, there are no uniquely hamiltonian graphs with girth 4 and minimum degree at least 3 on 18 (or less) vertices. See [1] for more details.

VerticesUHG's δ ≥ 3
0-170
182
191
202
2125
2233
Go to top

References

[1] J. Goedgebeur, B. Meersman and C.T. Zamfirescu, Graphs with few hamiltonian cycles, Mathematics of Computation, 89:965-991, 2020.

[2] G.F. Royle, The smallest uniquely hamiltonian graph with minimum degree at least 3 , 2017.


Copyright © 2010-2024 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close