Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428306 | Information Processing Letters | 2007 | 5 Pages |
Abstract
A Hamiltonian cycle is a closed path through all the vertices of a graph. Since discovering whether a graph has a Hamiltonian path or a Hamiltonian cycle are both NP-complete problems, researchers concentrated on formulating sufficient conditions that ensure Hamiltonicity of a graph. A recent paper [M.S. Rahman, M. Kaykobad, On Hamiltonian cycles and Hamiltonian paths, Information Processing Letters 94 (2005) 37–41] presents distance based sufficient conditions for the existence of a Hamiltonian path. In this paper we establish that the same condition forces Hamiltonian cycle to be present excepting for the case where end points of a Hamiltonian path is at a distance of 2.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics