Geodesic
On a Goodman–Hedetniemi sufficient condition for the graph Hamiltonicity
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 18 (2018) no. 3, pp. 347-353 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In 1859 the Irish mathematician Sir William Rowan Hamilton proposed a game in which it was required to find a dodecahedron bypass around its edges with a return to the starting point. In his honor, the corresponding path in the graph was later called the Hamiltonian cycle: it is the spanning cycle in the graph, that is, the cycle passing through all the vertices of the graph. A graph containing a Hamiltonian cycle is said to be Hamiltonian. In 1952 Dirac proposed a sufficient condition for the graph to be Hamiltonian: if the degree of each vertex is not less than half of the total number of vertices of the graph, then such a graph is Hamiltonian. Subsequently, many different sufficient conditions for Hamiltonicity were obtained, of which a large group is formed by so-called Dirac-type conditions or sufficient conditions formulated in terms of degrees of the vertices of the graph: sufficient conditions by Ore, Pocha, Chvatal and others. In 1976 Bondy and Chvatal proposed a closure construction for the graph and a new sufficient condition: if the closure of a graph is a complete graph, then the graph itself is Hamiltonian. This condition remains one of the most effective sufficient condition. In this paper, we will investigate the sufficient condition for the Hamiltonian graph by Goodman–Hedetniemi, which is formulated in terms of forbidden subgraphs. We give a description of all graphs that satisfy the Goodman–Hedetniemi condition and prove that for $n>4$ there are only $\left\lfloor n / 2 \right\rfloor + 2$ such $n$-vertex graphs. 
@article{ISU_2018_18_3_a9,
     author = {M. B. Abrosimov},
     title = {On a {Goodman{\textendash}Hedetniemi} sufficient condition for the graph {Hamiltonicity}},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {347--353},
     year = {2018},
     volume = {18},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2018_18_3_a9/}
}
TY  - JOUR
AU  - M. B. Abrosimov
TI  - On a Goodman–Hedetniemi sufficient condition for the graph Hamiltonicity
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2018
SP  - 347
EP  - 353
VL  - 18
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/ISU_2018_18_3_a9/
LA  - ru
ID  - ISU_2018_18_3_a9
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%T On a Goodman–Hedetniemi sufficient condition for the graph Hamiltonicity
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2018
%P 347-353
%V 18
%N 3
%U http://geodesic.mathdoc.fr/item/ISU_2018_18_3_a9/
%G ru
%F ISU_2018_18_3_a9
M. B. Abrosimov. On a Goodman–Hedetniemi sufficient condition for the graph Hamiltonicity. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 18 (2018) no. 3, pp. 347-353. http://geodesic.mathdoc.fr/item/ISU_2018_18_3_a9/

[1] Harary F., Graph Theory, Addison-Wesley, Reading, Mass., 1969, 274 pp. | MR | Zbl

[2] Dirac G. A., “Some Theorems on Abstract Graphs”, Proc. London Math. Soc., s3–2:1 (1952), 69–81 | DOI | MR | Zbl

[3] Ore O., “Note on Hamilton Circuits”, Amer. Math. Monthly, 67:1 (1960), 55 | DOI | MR | Zbl

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

[5] Posa L., “On the circuits of finite graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 8 (1963), 355–361 | MR

[6] Chvatal V., “On Hamilton's ideals”, J. Combinat. Theory (B), 12:2 (1972), 163–168 | DOI | MR | Zbl

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

[8] Fan G. H., “New sufficient conditions for cycles in graphs”, J. Combinat. Theory (B), 37:3 (1984), 221–227 | DOI | MR | Zbl

[9] Faudree R. J., Gould R. J., Jacobson M. S., Schelp R. H., “Neighborhood unions and Hamiltonian properties in graphs”, J. Combinat. Theory (B), 47:1 (1989), 1–9 | DOI | MR | Zbl

[10] Gould R. J., “Advances on the Hamiltonian Problem – A Survey”, J. Graph Theory, 15:2 (1991), 121–157 | DOI | MR | Zbl

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

[12] Goodman S. E., Hedetniemi S. T., “Sufficient Conditions for a graph to be Hamiltonian”, J. Combin Theory (B), 16:2 (1974), 175–180 | DOI | MR | Zbl