Hypohamiltonian graphs

Home CAAGT Authors Jan Goedgebeur Carol Zamfirescu

Hypohamiltonian graphs GenHypohamiltonian is a generator for hypohamiltonian and almost hypohamiltonian graphs. New: GenHypohamiltonian can now also be used to generate almost hypohamiltonian graphs. The algorithms used in the generator are described in: J. Goedgebeur and C.T. Zamfirescu, Improved bounds for hypohamiltonian graphs, Ars Mathematica Contemporanea, 13(2):235-257, 2017. J. Goedgebeur and C.T. Zamfirescu, On almost hypohamiltonian graphs, Discrete Mathematics and Theoretical Computer Science, 21(4), 18 pages, 2019. The generator can be downloaded here and a short manual can be found here. GenHypohamiltonian is released under the GNU General Public License (GPL) and has been tested on Linux and Mac OS X. Installation instructions: Download, extract and configure nauty (GenHypohamiltonian requires nauty 2.5 or a more recent version). Compile the nauty libraries using: "make nautyW1.a" Copy the following files to the GenHypohamiltonian directory: nausparse.h nauty.h nautyW1.a naututil.h planarity.c naurng.h splay.c planarity.h Compile using the command "make". The counts of hypohamiltonian graphs (including downloadable lists) can be found at the House of Graphs. The counts of almost hypohamiltonian graphs can be found at the here. The counts of platypus graphs can be found at the here. Don't hesitate to contact us at jan.goedgebeur[at]ugent.be if you have any further questions or suggestions.