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 offerthe 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

 

N Hamiltonian
Non-Hamiltonian
 4  1 : el, adj, asc, g6, ind  0
 6  2 : el, adj, asc, g6, ind  0
 8  5 : el, adj, asc, g6, ind  0
 10  17 : el, adj, asc, g6, ind  2 : el, adj, asc, g6, ind
 12  80 : el, adj, asc, g6, ind  5 : el, adj, asc, g6, ind
 14  474 : el, adj, asc, g6, ind  35 : el, adj, asc, g6, ind
 16  3841 : el, adj, asc, g6, ind  219 : el, adj, asc, g6, ind
 18  39635 : el, asc, g6, ind  1666 : el, adj, asc, g6, ind
 20  495991 : ind  14498 : el, asc, g6, ind
 22  7170657  148790 : g6
 24  117940535  1768732

 

 

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.