logo

Hypohamiltonian graphs

A graph G is hypohamiltonian if G is non-hamiltonian and G-v is hamiltonian for every vertex v of G.

The graph lists are currently only available in 'graph6' format.

Reza Jooyandeh also maintains a page with lists of planar hypohamiltonian graphs. This page can be found here .

Lists of almost hypohamiltonian graphs can be found here and lists of K2-hypohamiltonian graphs can be found here.

Hypohamiltonian graphs

All results up to 17 vertices were independently verified by Aldred, McKay and Wormald [1] and Goedgebeur and Zamfirescu [2]. The results with more than 17 vertices were obtained with the program GenHypohamiltonian of Goedgebeur and Zamfirescu [2].

The following table gives the complete lists of all hypohamiltonian graphs with a given lower bound on the girth. The counts of cases which are indicated with a '≥' in the table are possibly incomplete. In all other cases the numbers are the counts of the complete sets of hypohamiltonian graphs.

VerticesGirth ≥ 3Girth ≥ 4Girth ≥ 5Girth ≥ 6Girth ≥ 7Girth ≥ 8
0-9000000
10111000
11000000
12000000
13111000
14000000
15111000
16444000
17000000
1814138000
19343434000
20?≥ 984000
21??85000
22??420000
23??85000
24??2530000
25???100
26???000
27????00
28???≥ 210
29????00
30????00
31-35?????0
Go to top

Cubic hypohamiltonian graphs

The graphs in this section were obtained by applying a generator for cubic graphs (see the cubic graphs page) and testing the generated graphs for hypohamiltonicity as a filter.

The following table give the complete lists of all cubic hypohamiltonian graphs with a given lower bound on the girth. (Note that cubic hypohamiltonian graphs must have girth at least 4). More information about these graphs can be found in [2].

VerticesGirth ≥ 4Girth ≥ 5Girth ≥ 6Girth ≥ 7
0-90000
101100
12-160000
182200
201100
223300
241000
261009600
28523421
3020213910
323042800
Go to top

Hypohamiltonian snarks

Lists of hypohamiltonian snarks can be found on the snarks page.


References

[1] R. Aldred, B. McKay and N. Wormald, Small hypohamiltonian graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 23:143-152, 1997.

[2] J. Goedgebeur and C.T. Zamfirescu, Improved bounds for hypohamiltonian graphs, Ars Mathematica Contemporanea, 13(2):235-257, 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