logo

Almost hypohamiltonian graphs

A graph G is hypohamiltonian if G is non-hamiltonian and G-v is hamiltonian for every vertex v of G. A graph G is almost hypohamiltonian if G is non-hamiltonian and there exists a vertex w of G such that G-w is non-hamiltonian and G-v is hamiltonian for every vertex v of G different from w.

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

Lists of hypohamiltonian graphs can be found here.

The counts of incomplete cases are indicated with a '≥' in the table. In all other cases the numbers are the counts of the complete sets of almost hypohamiltonian graphs.

Almost hypohamiltonian graphs

All results were obtained with the program GenHypohamiltonian of Goedgebeur and Zamfirescu [1]

The following table gives the complete lists of all almost hypohamiltonian graphs with a given lower bound on the girth.

VerticesGirth ≥ 3Girth ≥ 4Girth ≥ 5Girth ≥ 6
0-160000
172220
182210
19?2740
20??140
21??270
22??1330
23??4040
24??≥680
25-26???0
Go to top

Cubic almost 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 almost hypohamiltonicity as a filter.

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

VerticesGirth ≥ 4Girth ≥ 5Girth ≥ 6
0-24000
2610100
28620
3025120
327440
Go to top

References

[1] J. Goedgebeur and C.T. Zamfirescu, On almost hypohamiltonian graphs, Discrete Mathematics and Theoretical Computer Science, 21(4), 18 pages, 2019.

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