On a Goodman--Hedetniemi sufficient condition for the graph Hamiltonicity

M. B. Abrosimov

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 18 (2018) no. 3, pp. 347-353.

Résumé

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.

Bibliographie

[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