A Fan-type result on k-ordered graphs
For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. In this paper, we show that if G is a left perpendicular3k/2right perpendicular-connected graph of order n  = n for any two vertices u and v with d(u, v) = 2, then G is k-ordered hamiltonian. Our result implies the theorem of G. Chen et al. [Ars Combin. 70 (2004) 245-255) [1], which requires the degree sum condition for all pairs of non-adjacent vertices, not just those distance 2 apart. (C) 2010 Elsevier B.V. All rights reserved.
k-ordered graphs k-linked combinatorial problems