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.
Original language | English (US) |
---|---|
Pages (from-to) | 199-210 |
Number of pages | 12 |
Journal | Journal of Graph Theory |
Volume | 42 |
Issue number | 3 |
DOIs | |
State | Published - Mar 2003 |
Keywords
- Hamiltonian cycle
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics