Geodesic
On the Number of Non-Hamiltonian Graphs
Matematičeskie zametki, Tome 75 (2004) no. 5, pp. 702-710.

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

In this paper, maximal non-Hamiltonian graphs (MNH graphs), i.e., non-Hamiltonian graphs such that the addition of any new edge violates their property of being non-Hamiltonian are studied. It is shown that the study of MNH graphs can be reduced to the study of the so-called simplified MNH graphs. Restrictions on the structure of maximal cliques of simplified MNH graphs are obtained, the orders and the number of such graphs are estimated. 
@article{MZM_2004_75_5_a6,
     author = {P. V. Roldugin},
     title = {On the {Number} of {Non-Hamiltonian} {Graphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {702--710},
     publisher = {mathdoc},
     volume = {75},
     number = {5},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2004_75_5_a6/}
}
TY  - JOUR
AU  - P. V. Roldugin
TI  - On the Number of Non-Hamiltonian Graphs
JO  - Matematičeskie zametki
PY  - 2004
SP  - 702
EP  - 710
VL  - 75
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2004_75_5_a6/
LA  - ru
ID  - MZM_2004_75_5_a6
ER  - 
%0 Journal Article
%A P. V. Roldugin
%T On the Number of Non-Hamiltonian Graphs
%J Matematičeskie zametki
%D 2004
%P 702-710
%V 75
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2004_75_5_a6/
%G ru
%F MZM_2004_75_5_a6
P. V. Roldugin. On the Number of Non-Hamiltonian Graphs. Matematičeskie zametki, Tome 75 (2004) no. 5, pp. 702-710. http://geodesic.mathdoc.fr/item/MZM_2004_75_5_a6/

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

[2] Roldugin P. V., “Maksimalno negamiltonovye grafy”, Tretii Vserossiiskii simpozium po prikladnoi i promyshlennoi matematike, Tezisy dokladov, TVP, M., 2002, 238–239

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

[4] Kharari F., Teoriya grafov, Mir, M., 1973, s. 86–87

[5] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982, s. 210–219 | Zbl