Geodesic
Construction of maximally non-Hamiltonian graphs
Diskretnaya Matematika, Tome 15 (2003) no. 2, pp. 89-102 
P. V. Roldugin. Construction of maximally non-Hamiltonian graphs. Diskretnaya Matematika, Tome 15 (2003) no. 2, pp. 89-102. http://geodesic.mathdoc.fr/item/DM_2003_15_2_a6/
@article{DM_2003_15_2_a6,
     author = {P. V. Roldugin},
     title = {Construction of maximally {non-Hamiltonian} graphs},
     journal = {Diskretnaya Matematika},
     pages = {89--102},
     year = {2003},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_2_a6/}
}
TY  - JOUR
AU  - P. V. Roldugin
TI  - Construction of maximally non-Hamiltonian graphs
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 89
EP  - 102
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_2_a6/
LA  - ru
ID  - DM_2003_15_2_a6
ER  - 
%0 Journal Article
%A P. V. Roldugin
%T Construction of maximally non-Hamiltonian graphs
%J Diskretnaya Matematika
%D 2003
%P 89-102
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2003_15_2_a6/
%G ru
%F DM_2003_15_2_a6

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we study the maximally non-Hamiltonian graphs (MNH graphs), that is, the graphs whose property to be non-Hamiltonian ceases to exist as soon as an edge is added. We give rules how to construct MNH graphs which make it possible, starting from MNH graphs with some properties, to get MNH graphs of greater order.

[1] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, Moskva, 1990 | MR | Zbl

[2] Roldugin P. V., “Maksimalno negamiltonovy grafy”, Tezisy dokl. Tretego Vserossiiskogo simpoziuma po prikladnoi i promyshlennoi matematike, TVP, Moskva, 2002, 238–239

[3] Roldugin P. V., “Sistemy lineinykh neravenstv dlya maksimalno negamiltonovykh grafov”, Vestnik MGU lesa, 2003, no. 1, 110–126

[4] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR

[5] Bondy J. A., “Variations on the Hamiltonian theme”, Canad. Math. Bull., 14:1 (1972), 57–62 | MR

[6] Vandegriend B., Finding Hamiltonian cycles: algorithms, graphs and performance, Univ. Alberta, Canada, 1998