Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

For citation:

Abrosimov M. B. On a Goodman–Hedetniemi Sufficient 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

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 120)
Article type: 

On a Goodman–Hedetniemi Sufficient Condition for the Graph Hamiltonicity

Abrosimov Mikhail Borisovich, Saratov State University

In 1859 the Irish mathematician Sir William Rowan Hamilt onpropose daga mein which it was required to find 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 sufficient 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 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⌊n/2⌋+2 such n-vertex graphs.  

  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
Short text (in English):
(downloads: 155)