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]).
The following lists are available:
Vertices | girth ≥ 3 | girth ≥ 4 | girth ≥ 5 |
---|---|---|---|
3 | 1 | 0 | 0 |
4 | 2 | 1 | 0 |
5 | 3 | 1 | 1 |
6 | 12 | 2 | 1 |
7 | 49 | 3 | 1 |
8 | 482 | 11 | 3 |
9 | 6380 | 38 | 4 |
10 | 135252 | 250 | 10 |
11 | 3939509 | 2171 | 32 |
12 | 166800470 | 25518 | 167 |
13 | 9739584172 | 388854 | 899 |
14 | 818717312364 | 7283110 | 6470 |
15 | 95353226103276 | 171355621 | 55815 |
16 | ? | 4915591680 | 549981 |
17 | ? | 174203813967 | 6155795 |
18 | ? | 7526329299531 | 78520177 |
19 | ? | ? | 1123544810 |
20 | ? | ? | 18005054988 |
21 | ? | ? | 322434738089 |
22 | ? | ? | 6427598615569 |
Vertices | girth ≥ 3 | girth ≥ 4 | girth ≥ 5 |
---|---|---|---|
3 | 1 | 0 | 0 |
4 | 2 | 1 | 0 |
5 | 3 | 1 | 1 |
6 | 12 | 2 | 1 |
7 | 49 | 3 | 1 |
8 | 460 | 11 | 3 |
9 | 4994 | 33 | 4 |
10 | 68234 | 178 | 8 |
11 | 997486 | 1011 | 23 |
12 | 15582567 | 6816 | 91 |
13 | 253005521 | 47669 | 317 |
14 | 4250680376 | 352901 | 1353 |
15 | 73293572869 | 2680512 | 6473 |
16 | 1293638724177 | 20939433 | 30834 |
17 | ? | 166713951 | 148907 |
18 | ? | 1352143860 | 768178 |
19 | ? | 11129922982 | 3987517 |
20 | ? | ? | 20767030 |
21 | ? | ? | 110819167 |
22 | ? | ? | 599311836 |
23 | ? | ? | 3256610004 |
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).
Vertices | Nearly cubic UHG's |
---|---|
0-16 | 0 |
18 | 1 |
20 | 20 |
22 | 337 |
24 | 4592 |
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.
Vertices | UHG's δ ≥ 3 |
---|---|
0-17 | 0 |
18 | 2 |
19 | 1 |
20 | 2 |
21 | 25 |
22 | 33 |
[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.