| Article ID: | iaor1995688 |
| Country: | Switzerland |
| Volume: | 50 |
| Issue: | 1 |
| Start Page Number: | 281 |
| End Page Number: | 293 |
| Publication Date: | Sep 1994 |
| Journal: | Annals of Operations Research |
| Authors: | Jurkiewicz Samuel |
If a graph has ‘too many’ edges, it must be Hamiltonian. The paper shows how to construct graphs near the threshold: they have as many edges as possible without sacrificing planarity but are not Hamiltonian. The present construction is based on the concepts of independent sets and 1-toughness.