Geodesic
Comparison of sufficient degree based conditions for Hamiltonian graph
Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 55-63.

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

A graph $G$ is said to be Hamiltonian if it contains a spanning cycle, i.e. a cycle that passes through all of its vertices. The Hamiltonian cycle problem is NP-complete, and many sufficient conditions have been found after the first sufficient condition proposed by Dirac in 1952. In this paper for all graphs with a number of vertices up to 12, the most popular sufficient degree based conditions for Hamiltonian graph are compared: theorems by Dirac, Ore, Posa, Chvatal and Bondy-Chvatal. The number of graphs which satisfy each condition is counted. With the number of vertices from 3 to 12, the number of graphs satisfying the Dirac condition is 1, 3, 3, 19, 29, 424, 1165, 108376, 868311, 495369040; the number of graphs satisfying the Ore condition is 1, 3, 5, 21, 68, 503, 4942, 128361, 5315783, 575886211; the number of graphs satisfying the Posha condition is 1, 3, 6, 31, 190, 2484, 53492, 2683649, 216082075, 40913881116; the number of graphs satisfying the Chvatal condition is 1, 3, 6, 34, 194, 2733, 54435, 2914167, 218674224, 43257613552 and the number of graphs satisfying the Bondy — Chvatal condition is 1, 3, 7, 45, 352, 5540, 157016, 8298805, 802944311, 141613919605. This result is the best one: about 90 % of the Hamiltonian graphs satisfy condition proposed by Bondy and Chvatal in 1976. The FHCP Challenge Set is a collection of 1001 instances of the Hamiltonian Cycle Problem, ranging in size from 66 vertices up to 9528. All graphs from the FHCP Challenge Set were checked whether they satisfy considered conditions. It turned out that 11 graphs satisfy the Bondy — Chvatal condition: no. 59 (with 400 vertices), no. 72 (460), no. 79 (480), no. 84 (500), no. 90 (510), no. 96 (540), no. 128 (677), no. 134 (724), no. 150 (823), no. 162 (909), and no. 188 (with 1123 vertices). For these graphs we can check and find Hamiltonian cycle using Bondy–Chvatal's theorem with computational complexity $O(n^4)$ where $n$ is the number of graph vertices.
Keywords: Hamiltonian graph, Dirac's theorem, Ore's theorem, Posa's theorem, Chvatal's theorem, theorem by Bondy and Chvatal. 
@article{PDM_2019_3_a6,
     author = {M. B. Abrosimov},
     title = {Comparison of sufficient degree based conditions for {Hamiltonian} graph},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {55--63},
     publisher = {mathdoc},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_3_a6/}
}
TY  - JOUR
AU  - M. B. Abrosimov
TI  - Comparison of sufficient degree based conditions for Hamiltonian graph
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 55
EP  - 63
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_3_a6/
LA  - ru
ID  - PDM_2019_3_a6
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%T Comparison of sufficient degree based conditions for Hamiltonian graph
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 55-63
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_3_a6/
%G ru
%F PDM_2019_3_a6
M. B. Abrosimov. Comparison of sufficient degree based conditions for Hamiltonian graph. Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 55-63. http://geodesic.mathdoc.fr/item/PDM_2019_3_a6/

[1] Dirac G. A., “Some theorems on abstract graphs”, Proc. London Math. Soc., 2 (1952), 69–81 | DOI | MR | Zbl

[2] Ore O., “Note on Hamilton circuits”, Amer. Math. Monthly, 67 (1960), 55 | DOI | MR | Zbl

[3] Ore O., “Arc coverings of graphs”, Ann. Mat. Pura Appl., 55 (1961), 315–322 | DOI | MR

[4] Posa L., “On the circuits of finite graphs”, Magyar Tud. Akad. Mat. Kutatd Int. Kozl., 8 (1963), 355–361 | MR

[5] Chvatal V., “On Hamilton's ideals”, J. Combin. Theory, 12 (1972), 163–168 | DOI | MR | Zbl

[6] Bondy J. A., Chvatal V., “A method in graph theory”, Discr. Math., 15:2 (1976), 111–135 | DOI | MR | Zbl

[7] Gould R. J., “Updating the Hamiltonian problem — A survey”, J. Graph Theory, 15:2 (1991), 121–157 | DOI | MR | Zbl

[8] Gould R. J., “Advances on the Hamiltonian problem — A survey”, Graphs and Combinatorics, 19 (2003), 7–52 | DOI | MR | Zbl

[9] DeLeon M., “A study of sufficient conditions for Hamiltonian cycles”, Rose — Hulman Undergraduate Mathematics J., 1:1 (2000), 6, 129–145

[10] Li H., “Generalizations of Diracs theorem in Hamiltonian graph theory — A survey”, Discr. Math., 313 (2013), 2034–2053 | DOI | MR | Zbl

[11] Harary F., Graph theory, Mir Publ., M., 1973, 300 pp. (in Russian)

[12] Diestel R., Graph Theory, Springer Verlag, Heidelberg, 2017, 447 pp. | MR

[13] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lections on Graph Theory, Nauka, M., 1990, 384 pp. (in Russian) | MR

[14] Asanov M. O., Baranskij V. A., Rasin V. V., Discrete Mathematics: Graphs, Matroids, Algorithms, NIC RHD Publ., Izhevsk, 2001, 288 pp. (in Russian)

[15] Kasyanov V. N., Evstigneev V. A., Graphs in Programming: Processing, Visualization and Application, BHV-Peterburg Publ., SPb., 2003, 1104 pp. (in Russian)

[16] Omelchenko A. V., Graph Theory, MCCME Publ., M., 2018, 416 pp. (in Russian)

[17] Abrosimov M. B., “On a Goodman — Hedetniemi sufficient condition for the graph hamiltonicity”, Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 18:3 (2018), 347–353 (in Russian) | MR | Zbl

[18] McKay B. D., Piperno A., “Practical graph isomorphism. II”, J. Symbolic Computation, 2014, no. 60, 94–112 | DOI | MR | Zbl

[19] The On-Line Encyclopedia of Integer Sequences, , 2018 http://oeis.org

[20] Haythorpe M., “FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem”, Bulletin of the ICA, 83 (2018), 98–107 | MR | Zbl

[21] Reinelt G., TSPLIB, , 2018 http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ | Zbl