We have provided a series of Sparse graphs for free download here. Please cite the reference below if you are using the graphs.
Graph HC01 is the graph of a regular solid dodecahedron. The graph is 3-connected.
Graph HC02 was obtained from Graph HC01 through a sequence of edge operations – a Hamiltonian cycle was first uncovered in the latter, following which three edges were deleted and ten edges were added while preserving its Hamiltonian property.
Graph NHC01 is the Tutte graph – a non-Hamiltonian 3-connected cubic graph.
Graphs HC03 through HC07 and, NHC02 and NHC03 are derived by applying a sequence of edge addition or deletion operations to the Tutte graph.
In graphs NHC02 and NHC03, the subgraph comprising edges 44-48, 48-46, 46-49, 49-45, 46-47 and 47-43 precludes the presence of Hamiltonian cycle.
Reference
K. K. Lim, Y. S. Ong, M. H. Lim, X. Chen and A. Agarwal, “Hybrid Ant Colony Algorithm for Path Planning in Sparse Graphs”, Soft Computing Journal, pp. 1432-7643, Nov 2007. Available here as PDF file.
Sparse
Hamiltonian graphs
HC01:
|V| = 20, |E| = 30, E_{d}
» 0.1579 |
HC02:
|V| = 20, |E| = 37, E_{d}
» 0.1947 |
HC03:
|V| = 46, |E| = 71, E_{d}
» 0.0686 |
HC04:
|V| = 100, |E| = 197, E_{d}
» 0.0398 |
HC05: |V| =
100, |E| = 203, E_{d}
» 0.0410 |
HC06:
|V| = 100, |E| = 217, E_{d}
» 0.0438 |
Sparse Non-Hamiltonian graphs
NHC01: |V| = 46, |E| = 69, E_{d} »0.0667 |
NHC02:
|V| = 100, |E| = 197, E_{d} » 0.0398 |
NHC03: |V| = 100, |E| = 207, E_{d} » 0.0418 |