| Institution: | 1. Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee 38152;2. Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322;3. Department of Mathematics, University of Illinois, at Urbana-Champaign, Urbana, IL 61801
Institute of Mathematics, 630090 Novosibirsk, Russia;4. Department of Mathematics and Computer Science, Drew University, Madison, New Jersey 07940;5. Department of Mathematics and Computer Science, Freiberg University of Mining and Technology, D-09596 Freiberg, Germany;6. Department of Applied Mathematics, Nihon University, Tokyo 156, Japan |
| 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 |
