Degree conditions for k‐ordered hamiltonian graphs
Ralph J. Faudree, Ronald J. Gould, Alexandr V. Kostochka, Linda M. Lesniak, Ingo Schiermeyer, Akira Saito · Journal of Graph Theory · 2003
Abstract 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. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k‐ordered hamiltonian. Minimum degree conditions are also given for k‐ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003