×

zbMATH — the first resource for mathematics

On Hamiltonian cycles and Hamiltonian paths. (English) Zbl 1182.68142
Summary: A Hamiltonian cycle is a spanning cycle in a graph, i.e., a cycle through every vertex, and a Hamiltonian path is a spanning path. In this paper we present two theorems stating sufficient conditions for a graph to possess Hamiltonian cycles and Hamiltonian paths. The significance of the theorems is discussed, and it is shown that the famous Ore’s theorem directly follows from our result.

MSC:
68R05 Combinatorics in computer science
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy, J.A.; Chv√°tal, V., A method in graph theory, Discrete math., 15, 111-136, (1976) · Zbl 0331.05138
[2] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), MIT Press Cambridge, MA · Zbl 1158.68538
[3] Dirac, G.A., Some theorems on abstract graphs, Proc. London math. soc., 2, 69-81, (1952) · Zbl 0047.17001
[4] Garey, M.R.; Jhonson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company New York
[5] Hen, R., Another cycle structure theorem for Hamiltonian graphs, Discrete math., 199, 237-243, (1999) · Zbl 0923.05037
[6] van den Heuvel, J., Hamilton cycles and eigenvalues of graphs, Linear algebra appl., 226-228, 723-730, (1995) · Zbl 0846.05059
[7] Ore, O., Note on Hamiltonian circuits, Amer. math. monthly, 67, 55, (1960) · Zbl 0089.39505
[8] Plotnikov, A.D., One criterion of existence of a Hamiltonian cycle, Reliable comput., 4, 199-202, (1998) · Zbl 0894.05039
[9] Schelten, U.; Schiermeyer, I., Small cycles in Hamiltonian graphs, Discrete appl. math., 79, 201-211, (1997) · Zbl 0882.05082
[10] West, D.B., Introduction to graph theory, (2001), Prentice-Hall Englewood Cliffs, NJ
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.