Hypohamiltonian graphs




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, 21 pages (2016). Preprint: (arXiv).
  • J. Goedgebeur and C.T. Zamfirescu, New results on hypohamiltonian and almost hypohamiltonian graphs, 18 pages (2016). Preprint: (arXiv)

The generator can be downloaded here and a short manual can be found here. Snarkhunter 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 (including downloadable lists) 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.

Last update: June 13, 2016.