Geodesic
Flip-Flops in Hypohamiltonian Graphs
Canadian mathematical bulletin, Tome 16 (1973) no. 1, pp. 33-41

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
Chvátal, V. Flip-Flops in Hypohamiltonian Graphs. Canadian mathematical bulletin, Tome 16 (1973) no. 1, pp. 33-41. doi: 10.4153/CMB-1973-008-9
@article{10_4153_CMB_1973_008_9,
     author = {Chv\'atal, V.},
     title = {Flip-Flops in {Hypohamiltonian} {Graphs}},
     journal = {Canadian mathematical bulletin},
     pages = {33--41},
     year = {1973},
     volume = {16},
     number = {1},
     doi = {10.4153/CMB-1973-008-9},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1973-008-9/}
}
TY  - JOUR
AU  - Chvátal, V.
TI  - Flip-Flops in Hypohamiltonian Graphs
JO  - Canadian mathematical bulletin
PY  - 1973
SP  - 33
EP  - 41
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1973-008-9/
DO  - 10.4153/CMB-1973-008-9
ID  - 10_4153_CMB_1973_008_9
ER  - 
%0 Journal Article
%A Chvátal, V.
%T Flip-Flops in Hypohamiltonian Graphs
%J Canadian mathematical bulletin
%D 1973
%P 33-41
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1973-008-9/
%R 10.4153/CMB-1973-008-9
%F 10_4153_CMB_1973_008_9

[1] 1. Bondy, J. A., Variations on the Hamiltonian theme, Canad. Math. Bull. (1) 15 (1972), 57–62. Google Scholar

[2] 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] 3. Harary, F., Graph theory, Addison-Wesley, Reading, Mass., 1969. Google Scholar

[4] 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] 5. Lindgren, W. F., An infinite class of Hypohamiltonian graphs, Amer. Math. Monthly, 74 (1967), 1087–1088. Google Scholar

[6] 6. Tutte, W. T., A non-Hamiltonian graph, Canad. Math. Bull. 3 (1960), 1–5. Google Scholar

Cité par Sources :