Short manual of GenHypohamiltonian
----------------------------------
Author: Jan Goedgebeur (jan.goedgebeur@ugent.be)
In collaboration with Carol Zamfirescu
GenHypohamiltonian is a generator for hypohamiltonian and almost hypohamiltonian graphs.
This program has been tested on Linux and Mac OS X.
Installation
------------
The latest version of GenHypohamiltonian can be obtained from http://caagt.ugent.be/hypo/
- Download, extract and configure nauty from http://users.cecs.anu.edu.au/~bdm/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 GenHypohamiltonian using the command "make".
(Alternatively, compile GenHypohamiltonian using the command: cc -DWORDSIZE=32 -DMAXN=WORDSIZE -mpopcnt -O4 gen_hypohamiltonian.c planarity.c nautyW1.a -o gen_hypohamiltonian)
Usage
-----
An overview of all options can also be found by executing "./gen_hypohamiltonian -h".
Usage: ./gen_hypohamiltonian [options]
Valid options are:
g: Searches for graphs with girth at least .
planar: Only output planar graphs.
maxdeg : Only output graphs with max degree at most 3.
mod : Splits the generation in (more or less equally big) parts. Here part will be executed.
almostcomplete: Generate almost hypohamiltonian graphs (is exhaustive).
almostspecial: Heuristic which generates almost hypohamiltonian graphs (is faster than almostcomplete, but may be incomplete).
platypus: Generate platypus graphs (non-hamiltonian graphs for which every vertex-deleted subgraph is traceable).
The generated graphs are written to stdout and are encoded in multicode format (see Appendix A).
Don't hesitate to contact me at jan.goedgebeur@ugent.be if you have any further questions or suggestions.
Changelog
---------
2018-09-18: Fixed bug related to destroying type A obstructions. We reran all previously reported computations and no graphs were missed by the old version of the program.
2017-10-10: Added support for generating platypus graphs.
2016-06-13: Added support for generating almost hypohamiltonian graphs.
2016-02-19: First release.
Appendix A: definition of the multicode format
----------------------------------------------
This code is binary. The first entry is the number of vertices.
Vertices are numbered 1,...,n. For each vertex x there is a list of
neighbours with higher labels than x, followed by a zero.
The last list is always empty (there are no neighbours of n with a higher number than n),
therefore the last "list" is not followed by a zero.
After the last byte the next graph follows.
The codelength of a graph in multicode is number of vertices + number of edges.
More information about this format + a program to translate multicode to adjacency lists can be found at: http://hog.grinvin.org/Formats.action#multicode