A new sufficient condition for Hamiltonicity of graphs
Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u) + d(v) + delta(u, v) >= n + 1 for each pair of distinct non-adjacent vertices it and v in G, where S(u, v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad. (c) 2006 Elsevier B.V. All rights reserved.
hamiltonian paths combinatorial problems graphs hamiltonian cycles