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, Ed » 0.1579 HC02: |V| = 20, |E| = 37, Ed » 0.1947 HC03: |V| = 46, |E| = 71, Ed » 0.0686 HC04: |V| = 100, |E| = 197, Ed » 0.0398 HC05: |V| = 100, |E| = 203, Ed » 0.0410 HC06: |V| = 100, |E| = 217, Ed » 0.0438

Sparse Non-Hamiltonian graphs

 NHC01: |V| = 46, |E| = 69, Ed »0.0667 NHC02: |V| = 100, |E| = 197, Ed » 0.0398
 NHC03: |V| = 100, |E| = 207, Ed » 0.0418