Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-29T17:49:42.018Z Has data issue: false hasContentIssue false
  • English
  • Français

Flip-Flops in Hypohamiltonian Graphs

Published online by Cambridge University Press:  20 November 2018

V. Chvátal
V. Chvátal*
Affiliation:
Centre De Recherches Mathématiques,Montréal Québec
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Throughout this note, we adopt the graph-theoretical terminology and notation of Harary [3]. A graph G is hypohamiltonianif G is not hamiltonian but the deletion of any point u from G results in a hamiltonian graph G-u. Gaudin, Herz, and Rossi [2] proved that the smallest hypohamiltonian graph is the Petersen graph. Using a computer for a systematic search, Herz, Duby, and Vigué [4] found that there is no hypohamiltonian graph with 11 or 12 points. However, they found one with 13 and one with 15 points. Sousselier [4] and Lindgren [5] constructed independently the same sequence of hypohamiltonian graphs with 6k+10 points. Moreover, Sousselier found a cubic hypohamiltonian graph with 18 points. This graph and the Petersen graph were the only examples of cubic hypohamiltonian graphs until Bondy [1] constructed an infinite sequence of cubic hypohamiltonian graphs with 12k+10 points. Bondy also proved that the Coxeter graph [6], which is cubic with 28 points, is hypohamiltonian.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 16 , Issue 1 , March 1973 , pp. 33 - 41
Copyright
Copyright © Canadian Mathematical Society 1973

References

1. Bondy, J. A., Variations on the Hamiltonian theme, Canad. Math. Bull. (1) 15 (1972), 57–62.Google Scholar
2. Gaudin, T., Herz, J.-C. and Rossi, P., Solution du Problème no. 29, Rev. Française Informat Recherche Opérationnelle,8 (1964), 214–218.Google Scholar
3. Harary, F., Graph theory, Addison-Wesley, Reading, Mass., 1969.Google Scholar
4. Herz, J.-C., Duby, J.-J. and Vigué, F., Recherche systématique des graphes Hypohamiltoniens, in Theory of Graphs (edited by Rosenstiehl, P.), International Symposium, Rome (1966), 153–159.Google Scholar
5. Lindgren, W. F., An infinite class of Hypohamiltonian graphs, Amer. Math. Monthly, 74 (1967), 1087–1088.Google Scholar
6. Tutte, W. T., A non-Hamiltonian graph, Canad. Math. Bull. 3 (1960), 1–5.Google Scholar