Constructing dense graphs with unique Hamiltonian cycles

• Autores: MarkA.M. Lynch
• Localización: International journal of mathematical education in science and technology, ISSN 0020-739X, Vol. 43, Nº. 3, 2012, págs. 388-395
• Idioma: inglés
• DOI: 10.1080/0020739x.2011.599876
• Texto completo no disponible (Saber más ...)
• Resumen

  • It is not difficult to construct dense graphs containing Hamiltonian cycles, but it is difficult to generate dense graphs that are guaranteed to contain a unique Hamiltonian cycle. This article presents an algorithm for generating arbitrarily large simple graphs containing uniqueHamiltonian cycles. These graphs can be turned into dense graphs which are guaranteed to be not Hamiltonian by the removal of an edge from the cycle. The generated graphs are dense in the sense that average vertex degree of the graphs is just greater than half the number of vertices in the graph.