Degree conditions for k-ordered Hamiltonian graphs

Ralph J. Faudree, Ronald J. Gould, Alexandr V. Kostochka, Linda Lesniak, Ingo Schiermeyer, Akira Saito

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)199-210
Number of pages12
JournalJournal of Graph Theory
Volume42
Issue number3
DOIs
StatePublished - Mar 2003

Keywords

  • Hamiltonian cycle

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Degree conditions for k-ordered Hamiltonian graphs'. Together they form a unique fingerprint.

Cite this