Rahman and Kaykobad introduced a shortest distance based condition for finding the existence of Hamiltonian paths in graphs as follows: Let G be a connected graph with n vertices, and 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 , then G has Hamiltonian path. Rao Li proved that under the same condition, the graph is Hamiltonian or belongs to two different classes of graphs. Recently, Mehedy, Hasan and Kaykobad showed case by case that under the condition of Rahman and Kaykobad, the graph is Hamiltonian with exceptions for δ(u, v) =2. Shengjia Li et. al. mentions a graph to be Hamiltonian whenever d(u) + d(v) ≥ n − 1, for all δ(u, v) = 2, otherwise n is odd and the graph falls into a special class. This paper relates the results of Mehedy, Hasan and Kaykobad with the two exceptional classes of graphs introduced by Rao Li and the graph class introduced by Shengjia Li et. al. The paper also provides a thorough analysis of the graph classes and shows the characteristics of a graph when it falls into one of those classes.
展开▼
