Independent Production of Non Hamiltonian Graphs

The decision whether a graph is hamiltonian or not is known to be an NP-complete problem. The importance of this kind of problem motivate several researchers in heuristics development. However, problems arise in the evaluating of this heuristics, more often because it is difficult to produce independent data. In this paper we develop methods to produce non hamiltonian graphs, based on independence subsets and toughness arguments. We also present a family of non hamiltonian graphs with strong restrictions, that is, planar 1-tough non hamiltonan graphs with no separation triangles.