Uniquely hamiltonian graphs

Home CAAGT Authors Jan Goedgebeur Barbara Meersman Carol Zamfirescu

Uniquely hamiltonian graphs GenerateUHG is a generator for graphs with a given number k of hamiltonian cycles (which is especially efficient for small values of k). The algorithms used in the generator are described in: J. Goedgebeur, B. Meersman and C.T. Zamfirescu, Graphs with few hamiltonian cycles, Mathematics of Computation, 89:965-991, 2020 (arXiv). The generator can be downloaded here and a short manual can be found here. GenerateUHG 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 (GenerateUHG requires nauty 2.5 or a more recent version). Compile the nauty libraries using: "make nautyW1.a" Copy the following files to the GenerateUHG 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 uniquely hamiltonian graphs (i.e. graphs with exactly one hamiltonian cycle) can be found at the House of Graphs. Don't hesitate to contact us at jan.goedgebeur[at]ugent.be if you have any further questions or suggestions.