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) + δ(u, v) ≥ n + 1 for each pair of distinct non-adjacent vertices u and v in G, where δ(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.