GRAPH DATABASE

This graph repository is concerned primarily with giving separate sets of Hamiltonian and non-Hamiltonian graphs, as well as some TSP instances.

RESISTANCE TSP INSTANCES

In our paper “A Note on Using the Resistance-Distance Matrix to solve Hamiltonian Cycle Problem” we considered 20 difficult instances of HCP, and converted them to instances of Traveling salesman problem, where the weights by chosen by four different scheme. The 20 instances of HCP and 80 associated instances of TSP are available here.

SMALL CUBIC GRAPHS

For small numbers of vertices, we give the exact number of connected, non-isomorphic Hamiltonian and non-Hamiltonian graphs. For small instances we provide downloadable sets in several formats: edge-list, adjacency matrix, GENREG .ASC and graph6. We also provide indices of these graphs corresponding to the output provided by GENREG. For some of the larger sets we only offer the graphs in certain formats, or only the number of such graphs.

For information on GENREG, see: http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

For information on graph6 see: http://cs.anu.edu.au/~bdm/data/formats.html

The graphs on this page were originally produced by GENREG [1].

[1]  M. Meringer: Fast Generation of Regular Graphs and Construction of Cages. Journal of Graph Theory 30, 137-146, 1999.