Article ID Journal Published Year Pages File Type
420345 Discrete Applied Mathematics 2010 9 Pages PDF
Abstract

For a positive integer kk, a graph GG is kk-ordered if for every ordered set of kk vertices, there is a cycle that encounters the vertices of the set in the given order. If the cycle is also a Hamiltonian cycle, then GG is said to be kk-ordered Hamiltonian. We first show that if GG is a (k+1)(k+1)-connected, kk-ordered graph of order n≥4k+3n≥4k+3 and d(u)+d(v)≥n−1d(u)+d(v)≥n−1 for every pair of vertices uu and vv of GG with d(u,v)=2d(u,v)=2, then GG is kk-ordered Hamiltonian unless GG belongs to an exceptional class of graphs. The latter class is described in this paper. By this result, we prove that GG is kk-ordered Hamiltonian if GG has the order n≥27k3n≥27k3 and d(u)+d(v)≥n+(3k−9)/2d(u)+d(v)≥n+(3k−9)/2 for every pair of vertices uu and vv of GG with d(u,v)=2d(u,v)=2.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,