ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

#### For citation:

Abrosimov M. B. On a Goodman–Hedetniemi Sufﬁcient Condition for the Graph Hamiltonicity. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2018, vol. 18, iss. 3, pp. 347-353. DOI: 10.18500/1816-9791-2018-18-3-347-353, EDN: YBMQMH

Published online:
28.08.2018
Full text:
Language:
Russian
Article type:
Article
UDC:
519.17
EDN:
YBMQMH

# On a Goodman–Hedetniemi Sufﬁcient Condition for the Graph Hamiltonicity

Autors:
Abrosimov Mikhail Borisovich, Saratov State University
Abstract:

In 1859 the Irish mathematician Sir William Rowan Hamilt onpropose daga mein which it was required to ﬁnd a dodeca hedron 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 sufﬁcient condition for the graph to be Hamiltonian: if the degree of each vertex is not less than half ofthet ot a lnumber of vertice soft hegraph, then such a graphis Hamiltonian. Subsequently, many different sufﬁcient conditions for Hamiltonicity were obtained, of which a large group is formed by so-called Dirac-type conditions or sufﬁcient conditions formulated in terms of degrees of the vertices of the graph: sufﬁcient conditions by Ore, Pocha, Chvatal and others. In 1976 Bondy and Chvatal proposed a closure construction for the graph and a new sufﬁcient 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 sufﬁcient condition. In this paper, we will investigate the sufﬁcient 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⌊n/2⌋+2 such n-vertex graphs.

Key words:
References:
1. Harary F. Graph Theory. Reading, Mass., Addison-Wesley, 1969. 274 p. [Russ. ed. Moscow, Mir, 1973. 300 p.].
2. Dirac G. A. Some Theorems on Abstract Graphs // Proc. London Math. Soc. 1952. Vol. s3– 2, iss. 1. P. 69–81. DOI: https://doi.org/10.1112/plms/s3-2.1.69
3. Ore O. Note on Hamilton Circuits // Amer. Math. Monthly. 1960. Vol. 67, № 1. P. 55. DOI: https://doi.org/10.2307/2308928
4. Ore O. Arc coverings of graphs // Ann. Mat. Pura Appl. 1961. Vol. 55, iss. 1. P. 315–322. DOI: https://doi.org/10.1007/BF02412090
5. Posa L. On the circuits of finite graphs // Magyar Tud. Akad. Mat. Kutat´o Int. K¨ozl. 1963. Vol. 8. P. 355–361.
6. Chvatal V. On Hamilton’s ideals // J. Combinat. Theory (B). 1972. Vol. 12, iss. 2. P. 163– 168. DOI: https://doi.org/10.1016/0095-8956(72)90020-2
7. Bondy J. A., Chvatal V. A method in graph theory // Discrete Math. 1976. Vol. 15, iss. 2. P. 111–135. DOI: https://doi.org/10.1016/0012-365X(76)90078-9
8. Fan G. H. New sufficient conditions for cycles in graphs // J. Combinat. Theory (B). 1984. Vol. 37, iss. 3. P. 221–227. DOI: https://doi.org/10.1016/0095-8956(84)90054-6
9. Faudree R. J., Gould R. J., Jacobson M. S., Schelp R. H. Neighborhood unions and Hamiltonian properties in graphs // J. Combinat. Theory (B). 1989. Vol. 47, iss. 1. P. 1–9. DOI: https://doi.org/10.1016/0095-8956(89)90060-9
10. Gould R. J. Advances on the Hamiltonian Problem – A Survey // J. Graph Theory. 1991. Vol. 15, iss. 2. P. 121–157. DOI: https://doi.org/10.1002/jgt.3190150204
11. Li H. Generalizations of Diracs theorem in Hamiltonian graph theory – A survey // Discrete Math. 2013. Vol. 313, iss. 19. P. 2034–2053. DOI: https://doi.org/10.1016/j.disc.2012.11.025
12. Goodman S. E., Hedetniemi S. T. Sufficient Conditions for a graph to be Hamiltonian // J. Combin Theory (B). 1974. Vol. 16, iss. 2. P. 175–180. DOI: https://doi.org/10.1016/00958956(74)90061-6