%% This document created by Scientific Word (R) Version 3.0

\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Tue Mar 21 13:33:33 2000}
%TCIDATA{LastRevised=Thu Jul 06 10:35:25 2000}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Journal Articles\Standard LaTeX Article">}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\thispagestyle{empty}


\begin{document}


\title{Degree conditions for $k$-ordered hamiltonian graphs}
\author{Ralph J. Faudree\\Department of Mathematical Sciences \\University of Memphis\\Memphis, TN 38152
\and Ronald. J. Gould\\Depatment of Mathematics and Computer Science\\Emory University\\Atlanta, GA 30322
\and Alexandr V. Kostochka\thanks{The author would like to thank grant 99-01-00581
of the Russian Foundation for Fundamental Research and a Dutch-Russian
Cooperative Grant.}\\Department of Mathematics\\University of Illinois at Urbana-Champaign\\Urbana, IL 61801\\and\\Institute of Mathematics\\630090 Novosibirsk, Russia
\and Linda \ Lesniak\\Department of Mathematics and Computer Science\\Drew University\\Madison, NJ 07940
\and Ingo Schiermeyer\\Department of Mathematics and Computer Science\\Freiberg University of Mining and Technology\\D-09596 Freiberg, Germany
\and Akira Saito\\Department of Applied Mathematics\\Nihon University\\Tokyo 156, Japan}
\maketitle
\begin{abstract}
For a positive integer $k$, a graph $G$ is \textit{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\leq k\leq n/2,$ and $\deg
(u)+\deg(v)\geq 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.
\end{abstract}



\subsection{Introduction}

One of the most widely studied classes of graphs are hamiltonian graphs, that
is, graphs that possess spanning cycles. \ In this article, \ we consider a
special family of hamiltonian graphs known as $k$-ordered hamiltonian graphs.
\ A graph is \textit{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. \ This concept was introduced by Chartrand.
Clearly, every hamiltonian graph is $3$-ordered hamiltonian. \ \ Ng and
Schultz [5] showed the following.

\begin{theorem}
Let $G$ be a graph of order $n$ and let $k$ be an integer with $3\leq k\leq n
$. \ If $\deg(u)+\deg(v)\geq n+2k-6$ for every pair $u,v$ of nonadjacent
vertices of $G$, then $G$ is $k$-ordered hamiltonian.

\begin{corollary}
Let $G$ be a graph of order $n$ and let $k$ be an integer with $3\leq k\leq n
$. \ If $\deg(u)\geq n/2+k-3$ for every vertex $u$ of $G$, then $G$ is
$k$-ordered hamiltonian.
\end{corollary}
\end{theorem}

Corollary 2 is an analog of the well-known theorem of Dirac [1] that says that
every graph of order $n\geq3$ with minimum degree at least $n/2$ is
hamiltonian, and Theorem 1 is an analog of Ore's theorem [6] that says that
every graph of order $n\geq3$ such that $\deg(u)+\deg(v)\geq n$ for every pair
$u,v$ of nonadjacent vertices is hamiltonian. \ We note that the restriction
$n$ in the statement of Ore's theorem is simply twice the restriction $n/2$ in
the statement of Dirac's theorem. \ The same holds for Corollary 2 and Theorem 1.

Both bounds for $k$-hamiltonicity were improved for small $k$ with respect to
$n$. \ The first result was improved by J. Faudree, R. Faudree, Gould,
Jacobson and Lesniak [2] .

\begin{theorem}
Let $k\geq3$ be an integer and let \ $G$ be a graph of order $n\geq53k^{2}$.
\ If $\deg(u)+\deg(v)\geq n+(3k-9)/2$ for every pair $u,v$ of nonadjacent
vertices of $G$, then $G$ is $k$-ordered hamiltonian.
\end{theorem}

The second result was improved by Kierstead, S\'{a}rk\"{o}zy and Selkow [3] as follows.

\begin{theorem}
Let $k\geq2$ be an integer and let $G$ be a graph of order $n\geq11k-3$. \ If
$\deg(u)\geq\left\lceil \frac{n}{2}\right\rceil +\left\lfloor \frac{k}%
{2}\right\rfloor -1$ for every vertex $u$ of $G$, then $G$ is $k$-ordered hamiltonian.
\end{theorem}

We note that both of these bounds are sharp for the respective values of $k$.
\ Thus, a bit unexpectedly, for small $k$, the Dirac type bound does not
follow from the Ore type bound. \ 

Our main result says that the bound of Theorem 3 holds for every $k$.

\begin{theorem}
Let $k$ be an integer with $3\leq k\leq n/2$ and let $G$ be a graph of order
$n$. \ If $\deg(u)+\deg(v)\geq n+(3k-9)/2$ \ for every pair $u,v$ of
nonadjacent vertices of $G$, then $G$ is $k$-ordered hamiltonian.
\end{theorem}

\bigskip The bound in this theorem is sharp. \ Moreover, for large $k$ it
implies the bound of the Dirac type. \ Thus,

(a) for large $k$, the Ore type bound yields the Dirac type bound;

(b) for small $k$, the Ore type bound is more than twice the Dirac type bound; and

(c) for moderate $k$, the situation is not clear.

\section{Degree sum conditions}

The following concept will be useful in establishing the primary result of
this section. \ For a positive integer $k,$ a graph $G$ is \textit{k-ordered}
if for every \ sequence of $k$ vertices there is a cycle that encounters the
vertices of the sequence in the given order. \ The following lemma gives a
condition under which a $k$-ordered graph is $k$-ordered hamiltonian. \ The
proof uses the following notations. \ If $C$ is a cycle in a graph with an
understood orientation, and $S$ is a set of vertices of $C$, then $S^{+}$ and
$S^{-}$ denote the successors and predecessors of the vertices in $S$ on $C$,
respectively. \ If $S=\{x\}$, we simply write $x^{+}$ and $x^{-}.$ \ Also, if
$x$ and $y$ are vertices of $C$, then $x\vec{C}y$ denotes the path from $x$ to
$y$ along $C$ in the designated direction or, when appropriate, the vertex set
of this path. \ The notation $x\overleftarrow{C}y$ denotes the path from $x$
to $y$ in the opposite direction. \ Similar notation is used in the case of paths.

\begin{lemma}
If $G$ is a $k$-ordered, ($k+1)$-connected graph of order $n\geq3$ such that
$\deg(u)+\deg(v)\geq n$ for every pair $u,v$ of nonadjacent vertices of $G$,
then $G$ is $k$-ordered hamiltonian.
\end{lemma}

\begin{proof}
Let $x_{1},x_{2},...x_{k}$ be an ordered sequence of $k$ vertices of $G$.
\ Since $G$ is $k$-ordered, there is a cycle $C$ that encounters these
vertices in this order. \ Choose such a cycle $C$ such that $\left|
V(C)\right|  $ is as large as possible. Assume $V(C)\neq V(G)$ and let $H$ be
a component of $G-V(C)$. \ Since $G$ is $(k+1)$-connected, $\left|
N_{C}(H)\right|  \geq k+1$ and hence $\left|  N_{C}(H)\cap x_{i}\vec{C}%
x_{i+1}\right|  \geq2$ for some $i,1\leq i\leq k,$ where we consider
$x_{k+1}=x_{1}.$ \ We may assume $\left|  N_{C}(H)\cap x_{k}\vec{C}%
x_{1}\right|  \geq2$. \ Choose a pair of distinct vertices $y_{1},y_{2}$ in
$N_{C}(H)\cap x_{k}\vec{C}x_{1}$ so that $x_{k},y_{1},y_{2},$and $x_{1}$
appear in this order along $C$, and so that $y_{1}\vec{C}y_{2}$ is as short as
possible. \ Possibly $x_{k}=y_{1}$ or $y_{2}=x_{1}$. \ Let $z_{i}\in
N_{H}(y_{i})\;(i=1,2)$. \ Note that possibly $z_{1}=z_{2}$. \ Since $H$ is
connected, there exists a path $P$ from $z_{1}$to $z_{2}$ in $H$. \ Then
$C^{\prime}=y_{2}\vec{C}y_{1}z_{1}\vec{P}z_{2}y_{2}$ is a cycle which
encounters $x_{1},x_{2},...,x_{k}$ in this order. \ If $y_{2}=y_{1}^{+}$, then
$\left|  V(C^{\prime})\right|  >\left|  V(C)\right|  $, which contradicts the
maximality of $\left|  V(C)\right|  $. \ Therefore, $y_{2}\neq y_{1}^{+}$.
\ Note that possibly $y_{1}^{+}=y_{2}^{-}$. \ By the choice of $\ y_{1\text{
}}$and $y_{2}$, $N_{C}(H)\cap y_{1}^{+}\vec{C}y_{2}^{-}=\phi$. \ In
particular, $y_{1}^{+}z_{1}\notin E(G)$, and hence $\deg_{G}(y_{1}^{+}%
)+\deg_{G}(z_{1})\geq n$.

Let $A_{1}=N_{G}\left(  y_{1}^{+}\right)  -V(C)$, $A_{2}=N_{G}\left(
y_{1}^{+}\right)  \cap y_{2}\vec{C}y_{1}$, $A_{3}=N_{G}(y_{1}^{+})\cap
y_{1}^{+}\vec{C}y_{2}^{-}$, $B_{1}=N_{G}\left(  z_{1}\right)  -V(C)$ and
$B_{2}=N_{G}\left(  z_{1}\right)  \cap y_{2}\vec{C}y_{1}$. \ Then
$N_{G}\left(  y_{1}^{+}\right)  $ is the disjoint union of $A_{1}$, $A_{2}$
and $A_{3}$, and since $N_{G}(z_{1})\cap y_{1}^{+}\vec{C}y_{2}^{-}=\phi$,
$N_{G}(z_{1})$ is the disjoint union of $B_{1}$ and $B_{2}$. \ If $A_{1}\cap
B_{1}\neq\phi$, say $v\in A_{1}\cap B_{1}$, then $v\in V(H)$ since $v\in
N_{G}(z_{1})$. \ However, this implies $y_{1}^{+}\in N_{C}(H)$, which
contradicts the fact that $N_{C}(H)\cap y_{1}^{+}\vec{C}y_{2}^{-}=\phi$.
\ Thus, we have $A_{1}\cap B_{1}=\phi$. \ Since $z_{1}\notin A_{1}\cup B_{1}$,
we have $n-\left|  V(C)\right|  -1\geq\left|  A_{1}\cup B_{1}\right|  =\left|
A_{1}\right|  +\left|  B_{1}\right|  $. \ Furthermore, since $y_{1}^{+}\notin
A_{3}$, we have $\left|  A_{3}\right|  \leq\left|  y_{1}^{+}\vec{C}y_{2}%
^{-}\right|  -1$. \ Therefore, we have%

\begin{align*}
n  &  \leq\deg_{G}(y_{1}^{+})+\deg_{G}(z_{1})=\left|  A_{1}\right|  +\left|
A_{2}\right|  +\left|  A_{3}\right|  +\left|  B_{1}\right|  +\left|
B_{2}\right| \\
&  \leq n-\left|  V(C)\right|  -1+\left|  y_{1}^{+}\vec{C}y_{2}^{-}\right|
-1+\left|  A_{2}\right|  +\left|  B_{2}\right|  ,
\end{align*}
or $\left|  A_{2}\right|  +\left|  B_{2}\right|  \geq\left|  y_{2}\vec{C}%
y_{1}\right|  +2$.

Assume $\left|  B_{2}\right|  \geq\frac{1}{2}\left|  y_{2}\vec{C}y_{1}\right|
+1$. \ Then $\{v,v^{+}\}\subset N_{G}(z_{1})$ for some $v\in y_{2}\vec{C}%
y_{1}^{-}$, and $v^{+}\vec{C}vz_{1}v^{+}$ is a cycle which contains
$x_{1},x_{2},...,x_{k}$ in this order. \ However, this again contradicts the
maximality of $\left|  V(C)\right|  $. \ Therefore, $\left|  B_{2}\right|
\leq\frac{1}{2}(\left|  y_{2}\vec{C}y_{1}\right|  +1)$. \ This implies%

\[
\left|  A_{2}\right|  =\left|  N_{G}(y_{1}^{+})\cap y_{2}\vec{C}y_{1}\right|
\geq\frac{1}{2}\left|  y_{2}\vec{C}y_{1}\right|  +\frac{3}{2}.
\]

Applying the same arguments to $z_{2}$ and $y_{2}^{-}$ instead of $z_{1}$ and
\ $y_{1}^{+}$, we have $\left|  N_{G}(y_{2}^{-})\cap y_{2}\vec{C}y_{1}\right|
\geq\frac{1}{2}\left|  y_{2}\vec{C}y_{1}\right|  +\frac{3}{2}$. \ Let $X$
$\ =(N_{G}(y_{1}^{+})\cap y_{2}^{+}\vec{C}y_{1})^{-}$ and $Y=N_{G}(y_{2}%
^{-})\cap y_{2}\vec{C}y_{1}$. \ Since%

\[
\left|  X\right|  =\left|  X^{+}\right|  =\left|  N_{G}(y_{1}^{+})\cap
y_{2}^{+}\vec{C}y_{1}\right|  \geq\frac{1}{2}\left|  y_{2}\vec{C}y_{1}\right|
+\frac{1}{2}%
\]
and $X\cup Y\subset y_{2}\vec{C}y_{1}$,%

\begin{align*}
\left|  X\cap Y\right|   &  =\left|  X\right|  +\left|  Y\right|  -\left|
X\cup Y\right| \\
&  \geq\frac{1}{2}\left|  y_{2}\vec{C}y_{1}\right|  +\frac{1}{2}+\frac{1}%
{2}\left|  y_{2}\vec{C}y_{1}\right|  +\frac{3}{2}-\left|  y_{2}\vec{C}%
y_{1}\right|  =2
\end{align*}
and hence $X\cap Y\neq\phi$. \ Let $v\in X\cap Y$. \ Then $v^{+}\in
N_{G}(y_{1}^{+})\cap y_{2}^{+}\vec{C}y_{1}$. \ Let%

\[
C^{\prime\prime}=y_{1}z_{1}\vec{P}z_{2}y_{2}\vec{C}vy_{2}^{-}\overleftarrow
{C}y_{1}^{+}v^{+}\vec{C}y_{1}.
\]
Then $C^{\prime\prime}$ contains $x_{1},x_{2},...,x_{k}$ in this order and
$\left|  V(C^{\prime\prime})\right|  >\left|  V(C)\right|  $. \ (Note that the
arguments are valid even if $y_{2}^{-}=y_{1}^{+}$.) \ This contradicts the
maximality of $\left|  V(C)\right|  $, and the lemma follows.
\end{proof}

\bigskip Lemma 6 can now be used to improve the result of \ Theorem 3. \ For
convenience, we restate Theorem 5 here as Theorem 7. \ \ 

\begin{theorem}
Let k be an integer with $3\leq k\leq n/2$ and let $G$ be a graph of order
$n.$ If $\deg(u)+\deg(v)\geq n+(3k-9)/2$ for every pair $u,v$ of nonadjacent
vertices of $G$, then \ $G$ is $k$-ordered hamiltonian.
\end{theorem}

\begin{proof}
By the assumptions \ of the theorem, $G$ is hamiltonian and, hence,
$k$-ordered hamiltonian for $k\leq3$. \ Thus we may assume that $k\geq4$.
\ Furthermore, the assumed degree conditions imply that $G$ is $(k+1)$%
-connected unless $k=3$ or $4.$ \ In these cases it is straightforward to
check that \ $G$ is $k$-ordered hamiltonian. \ Thus we may assume that $G$ is
$(k+1)$-connected and, by the previous lemma, it suffices to show that $G$ is
$k$-ordered.

Let $K=\{x_{1},x_{2},...,x_{k}\}$ be an ordered sequence of $k$ vertices of
$G$. \ We show that $G$ contains a cycle that encounters these vertices in the
given order. \ Let $W$ be the set of indices $i$ such that $x_{i}x_{i+1}\in
E(G)$ and $w=\left|  W\right|  $. A \textit{1-improvement of size s} of $G$ is
a set of vertices $S=\{y_{1},y_{2},...,y_{s}\}\subset V(G)-K$ and a set of
indices $\{i_{1},i_{2},...,i_{s}\}$ such that for every $j=1,2,...,s$, \ we
have that $x_{i_{j}}x_{i_{j}+1}\notin E(G)$ and $y_{j}$ is adjacent to both
$x_{i_{j}}$and $x_{i_{j}+1}$. \ The indices \ $i_{1},i_{2},...,i_{s}$ will be
called \textit{S-indices.} \ For \ $\ i=1,2,...,k$, let $\delta(i)=1$ if
neither of the edges $x_{i-1}x_{i}$ and $x_{i}x_{i+1}$ is in $E(G)$, and,
otherwise, $\delta(i)=0$.

\begin{claim}
There is a 1-improvement of size s $\geq3k-n-2w.$
\end{claim}

Consider the auxiliary bipartite graph H with partite sets $P$ and $Q$, where
$Q=V(G)-K,$ and
\[
P=\{\{x_{i},x_{i+1}\}:i\in\{1,2,...,k\}\backslash W\text{, where }%
k+1\equiv1\},
\]
and a vertex $\{x_{i},x_{i+1}\}\in P$ is adjacent to a vertex $q\in Q$ if and
only if $q$ is a common neighbor of $x_{i}$ and $x_{i+1}$ in $G$. \ By the
construction of $H$, $s$ is the size of a maximum matching in $H.$ \ By Ore's
theorem or, more generally , by Berge's theorem on maximum matchings (see
[4]), there exists $T\subset P$ such that
\[
\left|  N_{H}(T)\right|  =\left|  T\right|  -(k-s-w)\text{.}%
\]

Let $\{x_{i},x_{i+1}\}\in T$ such that $\delta(i)+\delta(i+1)$ is maximum.
\ Let $L=Q-N_{H}(T)$. \ By definition, \ $L=(L-N_{G}(x_{i}))\cup
(L-N_{G}(x_{i+1})).$ \ We may assume that
\[
\left|  L-N_{G}(x_{i})\right|  \geq\left|  L-N_{G}(x_{i+1})\right|  \text{
\ \ \ (1)}%
\]
and that $y\in L-N_{G}(x_{i}).$

By (1),
\[
\deg_{G}(x_{i})\leq n-2-\delta(i)-\left|  L\right|  /2
\]
and $\deg_{G}(y)\leq n-1-(\left|  T\right|  +1-\delta(i))/2.$ Since
$x_{i}y\notin E(G)$, we conclude that%

\[
n+\frac{3k-9}{2}\leq(n-2-\delta(i)-\frac{\left|  L\right|  }{2})+(n-1-\frac
{\left|  T+1-\delta(i)\right|  }{2})=2n-
\]%

\[
\frac{\left|  T\right|  +7+\delta(i)+n-k-\left|  N_{H}(T)\right|  }%
{2}=2n-\frac{\left|  T\right|  +7+\delta(i)+n-k-\left|  T\right|  +k-s-w}{2}.
\]
Hence,%

\[
n+\frac{3k-9}{2}-2n+\frac{7+n-s-w+\delta(i)}{2}\leq0.\text{ \ \ (2)}%
\]

CASE 1. \ Suppose \ $w+\delta(i)\geq2.$ \ Then we are finished by (2).

CASE 2. $\;$Suppose $w=0.$ Then $\delta(j)=1$ for every $j.$ \ In particular,
$\delta(i)=1.$ \ Thus, if the inequality in (2) is strict, then we are done.
\ In order to have equality in (2), we must have

(a) \ $\left|  L-N_{G}(x_{i})\right|  =\left|  L\right|  /2$, so $\left|
L\right|  $ is even and, in view of (1), $L-N_{G}(x_{i})=L\cap N_{G}(x_{i+1})
$;

(b) $3k-9$ is even (and hence $k$ is odd);

(c) \ $\deg_{G}(y)=n-1-\left|  T\right|  /2,$ so that $\left|  T\right|  $ is even;

(d) \ every nonedge at $y$ must ''spoil'' exactly two elements of $T$ \ in
order to have $\deg_{G}y=n-1-\left|  T\right|  /2$; in particular, the pair
($x_{i-1},x_{i})$ must be in $T.$

Because of (a), the roles of \ $x_{i}$ and $x_{i+1}$ are interchangeable, and
hence ($x_{i+1},x_{i+2})$ must be in $T$. \ \ Applying the above reasoning to
the pair ($x_{i+1},x_{i+2})$ we get that ($x_{i+2},x_{i+3})\in T $, and so on.
\ It follows that \ $T=P$ and, since $W=\emptyset$, $\ \left|  T\right|  =k$.
\ Then by (c), $k$ is even, a contradiction to (b).

CASE 3. \ Suppose $w=1$ and $\delta(i)=0.$ \ This is possible only if $i-1$ is
the unique index in $W.$ \ Because of the choice of $i$, we get $\left|
T\right|  \leq2.$ \ Thus, $\left|  N_{H}(T)\right|  \leq2-(k-s-w).$ \ On the
other hand, since $x_{i}x_{i+1}\notin E(G),$%

\[
\left|  N_{H}(T)\right|  \geq\left|  N_{G}(x_{i})\cap N_{G}(x_{i+1})-K\right|
\geq
\]%
\[
n+\frac{3k-9}{2}-(n-2)-(k-2)+\delta(i)+\delta(i+1)=\frac{k+1}{2}.
\]
Since $k-s-w\geq0$, we get $(k+1)/2\leq2$. \ This is posssible only for
$k\leq3$, which is impossible since $k\geq4$. \ This proves Claim 7.

.

Let $(S,\{i_{1},i_{2},...,i_{s})\}$ be a 1-improvement of $G$. \ Construct the
auxiliary bipartite graph $F$ as follows. \ One partite set of $F$ is
$M=V(G)-K-S$ . \ The other partite set of $F$ is $R.$ \ In order to define
$R$, let $I=\{1,2,...,k\}\backslash\{i_{1},i_{2},...,i_{s}\}\backslash W.$
Then
\[
R=\cup_{I}\{(i,x_{i}),(i,x_{i+1})\}.
\]
We join $\ v\in M$ with $(i,x_{j})\in R$ if and only if $vx_{j}\in E(G).$
\ Note that $\left|  R\right|  =2(k-s-w)$. \ Call a pair ($i,x_{j})\in R$
\textit{senior} if $x_{j}$ is adjacent in $G$ to at least $k-w$ vertices in
$V(G)-K$, and \textit{junior}, otherwise.

\begin{claim}
If S is a 1-improvement of maximum size, then the auxiliary graph F contains a
matching covering all senior elements of R.
\end{claim}

If there is no such matching, then there exists $T\subset R$ consisting of
senior vertices with $\left|  N_{F}(T)\right|  \leq\left|  T\right|  -1.$

CASE 1. Suppose there is an $i$ such that $(i,x_{i})\in T$ and $(i,x_{i+1})\in
T$, say $i=1$. \ Due to the maximality of $S$, \ $(N_{G}(x_{1})\cap
N_{G}(x_{2}))-K\subseteq S.$ Hence, $\left|  N_{F}(T)\right|  \geq
(k-w)+(k-w)-2s=\left|  R\right|  $, a contradiction to the choice of $T$.

CASE 2. \ Suppose $\left|  T\right|  \leq k-s-w.$ \ Let $(i,x_{j})\in T.$
\ Since $(i,x_{j})$ is senior, $x_{j}$ is adjacent in $G$ to at least $k-w-s$
vertices in $V(G)-K-S.$ \ \ Therefore, $\left|  N_{F}(T)\right|  \geq
k-s-w\geq\left|  T\right|  $, again a contradiction to the choice of $T$.

\begin{claim}
If S is a 1-improvement of maximum size, then the auxiliary graph F contains a
matching covering all elements of R.
\end{claim}

By Claim 7, $\left|  R\right|  $\ \ $=2(k-s-w)\leq
2k-s-2w-(3k-n-2w)=n-k-s=\left|  M\right|  $, and hence by Claim 8 we can
assign to every $(i,x_{i})\in R$ a vertex $z_{i,1}$ and to every
$(i-1,x_{i})\in R$ a vertex $z_{i-1,2}$ so that $x_{i}z_{i,1}\in E(G)$
provided that $(i,x_{i})$ is senior and $x_{i}z_{i-1,2}\in E(G)$ provided that
$(i-1,x_{i})$ is senior. \ Among all such assignments choose one with the
maximum number of edges of the form $x_{i}z_{i,1}$ and $x_{i}z_{i-1,2}$. \ We
will show that all edges of this kind exist in $G$ which will prove the claim.

Assume that, say, \ $x_{1}$ is not adjacent to $z_{1,1}$. \ Recall then that
$(1,x_{1})$ is junior. \ Let $Z_{i}=\{z_{i,1},z_{i,2}\}$ and $Z=\cup_{i=1}%
^{k}Z_{i}.$ \ Let $Z^{\ast}$ be the set of vertices in $Z$ adjacent to $x_{1}$
and let $S^{\ast}$ be the set of vertices in $S$ adjacent to $x_{1}.$ \ If
some $z_{i,1}\in Z^{\ast}$ and $z_{1,1}x_{i}\in E(G),$ then we can switch
$z_{i,1}$ with $z_{1,1}$ and have $z_{1,1}x_{1}\in E(G),$ maintaining the
desired properties. \ Thus, in this case, $z_{1,1}x_{i}\notin E(G)$.
\ Similarly, $z_{1,1}x_{i+1}\notin E(G)$ if $z_{i,2}x_{1}\in E(G).$ \ By the
maximality of $S$, if $y_{j}\in S^{\ast}$, then $z_{1,1}$ is not adjacent to
both $x_{i_{j}}$ and $x_{i_{j+1}}$, but possibly one of them. \ Therefore,
since $z_{1,1}\notin Z^{\ast}$, it follows that $\deg(z_{1,1})\leq
n-1-(\left|  S^{\ast}\right|  +\left|  Z^{\ast}\right|  +(1-\delta(1)))/2$,
where one missing edge can be used twice, and
\[
n+\frac{3k-9}{2}\leq\deg(x_{1})+\deg(z_{1,1})\leq(k-2-\delta(1)+\left|
S^{\ast}\right|  +\left|  Z^{\ast}\right|  )+
\]%

\[
(n-1-\frac{\left|  S^{\ast}\right|  +\left|  Z^{\ast}\right|  +2-\delta(1)}%
{2})=n+k-4+\frac{\left|  S^{\ast}\right|  +\left|  T^{\ast}\right|
-\delta(1)}{2}.
\]
It follows that \ $k\leq\left|  S^{\ast}\right|  +\left|  T^{\ast}\right|
+1-\delta(1).$ \ Since $x_{1}$ is junior, $\left|  S^{\ast}\right|  +\left|
T^{\ast}\right|  \leq k-1-w$ and thus $k\leq k-w-\delta(1).$ \ But if $w=0$,
then $\delta(1)=1$. \ This contradiction proves the Claim 9.

We now complete the proof of the theorem. \ Claim 9 says that we can assume
that for every $i=1,2,...,k$ there is either $y_{i}\in S$ adjacent to both
$x_{i}$ and $x_{i+1}$ in the case $x_{i}x_{i+1}\notin E(G)$ or there are two
vertices $z_{i,1}\in N_{G}(x_{i})$ and $z_{i,2}\in N_{G}(x_{i+1}).$
\ Moreover, all the $y_{i}$ and $z_{i,j}$ are distinct. \ Let $Z_{i}%
=\{z_{i,1},z_{i,2}\}$ and $Z=\cup_{i=1}^{k}Z_{i}$. \ Among all such
assignments, choose one with the maximum number of edges of the kind
\ $z_{i,1}z_{i,2}$. \ We will show that all edges of this kind exist, which
will imply the theorem.

Assume that in our assignment there is an $i$ such that $z_{i,1}z_{i,2}\notin
E(G),$ say i = 1. \ Let $P=V(G)-K-S-Z.$ \ By the maximality \ of $S$ , no
vertex in $P$ is adjacent to both $x_{1}$and $x_{2}$.\ Let $P_{0}$ be the set
of vertices in $P$\ that are adjacent to neither $x_{1}$nor $x_{2}$, and for
$i=1,2$, let P$_{i}$ be the set of vertices in $P$ adjacent to $x_{i}.$ \ For
$i=0,1,2,$ let $p_{i}=\left|  P_{i}\right|  $. \ For $j=0,1,2,$ let $S_{j}$
denote the set of vertices in $S$ adjacent to exactly $j$ of the vertices
$x_{1}$ and $x_{2}$ and let $s_{j}=\left|  S_{j}\right|  $.

Since $x_{1}x_{2}\notin E(G)$, $\deg(x_{1})+\deg(x_{2})\geq n+(3k-9)/2.$
\ Recall that by the maximality of $S$, no vertex in $Z$ is adjacent to both
$x_{1}$ and $x_{2}.$ \ It follows that
\[
n+\frac{3k-9}{2}\leq\deg(x_{1})+\deg(x_{2})\leq(n-2)+(k-2)-\delta
(1)-\delta(2)+s_{2}-s_{0}-p_{0,}%
\]
and hence
\[
s_{2}\geq-0.5+\delta(1)+\delta(2)+s_{0}+p_{0}+k/2.
\]

Since $z_{1,1}$ and $z_{1,2}$ are nonadjacent, $\deg(z_{1,1})+\deg
(z_{1,2})\geq n+(3k-9)/2.$ \ On the other hand, $z_{1,j}$ is adjacent to no
vertex in $P_{3-j}$ ($j=1,2$). \ Furthermore, for every $Z$-index or $S_{2}%
$-index $j$, each of $z_{1,1}$ and $z_{1,2}$ is not adjacent to at least one
of $x_{j},x_{j+1}.$ \ It follows that
\[
n+\frac{3k-9}{2}\leq\deg(z_{1,1})+\deg(z_{1,2})\leq
\]%

\[
2(n-2)-p_{2}-p_{1}-s_{2}-\frac{\left|  Z\right|  +(1-\delta(1))+(1-\delta
(2))}{2},
\]
and hence
\[
3k/2+0.5+p_{1}+p_{2}+s_{2}+\frac{\left|  Z\right|  -\delta(1)-\delta(2)}%
{2}\leq n.
\]
Recall that
\[
s_{2}\geq-0.5+\delta(1)+\delta(2)+s_{0}+p_{0}+k/2.
\]
Hence
\[
2k+2+s_{0}+p_{0}+p_{1}+p_{2}+\frac{\left|  Z\right|  }{2}+\frac{\delta
(1)+\delta(2)}{2}\leq n.
\]
But
\[
p_{0}+p_{1}+p_{2}+\frac{\left|  Z\right|  }{2}=\left|  V(G)-K-S\right|
-\frac{\left|  Z\right|  }{2}=n-k-(k-w)=n-2k+w.
\]

These last two statements imply that $2k+n-2k+n+w+\frac{\delta(1)+\delta
(2)}{2}\leq n$, which in turn gives $w+\frac{\delta(1)+\delta(2)}{2}\leq0.$
\ But by the definitions of $w$ and $\delta(1),$ we have $w+\frac
{\delta(1)+\delta(2)}{2}\geq1$. \ This contradiction completes the proof of
the theorem.
\end{proof}

\begin{corollary}
Let $k$ be an integer with 3 $\leq k\leq n/2$ and let $G$\ be a graph of order
$n$. If $\deg(v)\geq n/2+\frac{3k-9}{4}$ for every vertex $v$ of $G$, then $G$
is $k$-ordered hamiltonian.
\end{corollary}

\bigskip

That \ Theorem 7 is sharp is indicated by the following example which was
mentioned in [5]. \ The graph $G$ with $n$ vertices is composed of \ three
parts : copies of $K_{k-1},$ $K_{k}-C_{k}$, and $K_{n-2k+1}$, where the
vertices of the ''missing''cycle $C_{k}$ are indexed in the natural
order.\ Further, $G$ contains all the edges between the copies of $K_{k-1}$and
$K_{n-2k+1}$, and all of the edges between the copies of $K_{k-1}$ and
$K_{k}-C_{k}$. \ Between the copies of $K_{n-2k+1}$ and $K_{k}-C_{k}$, $G$
contains all edges incident to the even indexed vertices of $C_{k}$. \ This
graph is not $k$-ordered because there is no cycle containing the vertices of
$C_{k}$ in order. \ However, when $k$ is even, if $u\in V(K_{n-2k+1})$ and
$v\in V(K_{k}-C_{k})$, where $v$ is an odd-indexed vertex, $\deg
(u)+\deg(v)=n+\frac{3k-10}{2}.$

\section{Minimum degree conditions}

In this section we consider minimum degree conditions that guarantee that a
graph is $k$-ordered hamiltonian. \ The main interest in such results follows
from the following observation. \ Theorem 7 gives a result based on the degree
sums of nonadjacent vertices of a graph of order $n$. \ Here we have the
condition for $3\leq k\leq n/2$, that if $\deg(u)+\deg(v)\geq n+(3k-9)/2$
\ for all nonadjacent vertices $u$ and $v$ of a graph $G$, then $G$ is
$k$-ordered hamiltonian. \ However, Theorem 4 gives a minimum degree result
that says that for $n\geq11k-3$, if $\deg(u)\geq\left\lceil \frac{n}%
{2}\right\rceil +\left\lfloor \frac{k}{2}\right\rfloor -1$ for every vertex
$u$ of a graph $G$, then $G$ is $k$-ordered hamiltonian. \ Both of these
results are sharp. \ However, the bound given in Theorem 7 is not twice the
bound given in Theorem 4, unlike most results of this nature. \ So an obvious
questions is, for all $n$ and $k$, what minimum degree condition implies that
a graph $G$ is $k$-ordered hamiltonian?

\ In the previous sections we have seen two such results, the aforementioned
Theorem 4 for values of $n,k$ satisfying $n\geq11k-3$, and Corollary 11 for
values of $n,k$ satisfying $k\leq n/2.$ It is also obvious that for
$n/2<k\leq2n/3$ , minimum degree at least $n-2$ guarantees a $k$-ordered
hamiltonian graph, and that for $k>2n/3$ (and in fact for any $k$), minimum
degree $n-1$ gives a $k$-ordered hamiltonian graph. \ \ The main object of
this section is to provide examples that discuss the sharpness of these known results.

For $2\leq k\leq n/3$ , consider the graph $G$ that consists of three parts :
two copies of $K_{(n-k+2)/2}$ and a copy of $K_{k-2}$ , where $n$ and $k$ are
of the same parity. \ The vertices in the copy of $K_{k-2}$ are adjacent to
all other vertices of the graph. \ Then $G$ is not $k$-ordered hamiltonian
since $G$ is not $(k-1)$-connected, a necessary condition for a graph to be
$k$-ordered hamiltonian, and $\delta(G)$ is $\frac{n}{2}+\frac{k}{2}-2.$

For $n/3<k<2(n+2)/5$ , consider the graph $G$ that consists of three parts :
copies of $K_{3k-n-1},K_{2n-4k+1}$ and $K_{k}-C_{k}$, where the vertices of
the ''missing'' cycle are indexed in the natural order. \ $G$ contains all the
edges between the copy of $K_{3k-n-1}$ and the rest of the graph. \ The
vertices of $K_{2n-4k+1}$ are divided into two sets $A$ and $B,$where $\left|
A\right|  =n-2k+1$ and $\left|  B\right|  =n-2k.$ All vertices of $A$ are
adjacent to the even indexed vertices of $C_{k}$ and all vertices of $B$ are
adjacent to the odd indexed vertices of $C_{k}.$ \ Then $G$ is not $k$-ordered
hamiltonian since there is no hamiltonian cycle containing the vertices of
$C_{k}$ in order, and $\delta(G)$ $\ =2k-3.$

For $2(n+2)/5\leq k\leq n/2$, consider the graph that consists of three parts:
copies of $K_{k/2},K_{n-3k/2}$ and $K_{k}-C_{k}$, where the vertices of the
''missing'' cycle are indexed in the natural order and $k$ is even. \ The
vertices of $K_{n-3k/2}$ are as evenly as possible divided into two sets $A$
and $B.$ \ All vertices of $A$ are adjacent to the even indexed vertices of
$C_{k}$ and all vertices of $B$ are adjacent to the odd indexed vertices of
$C_{k}.$ In addition, there is a specified set of $5k/2-n-2$ consecutive
vertices of $C_{k}$ that are adjacent to all vertices of $A$ and $B$. \ Then
$G$ is not $k$-ordered hamiltonian since there is no hamiltonian cycle
containing the vertices of $C_{k}$ in order, and $\delta(G)=n/2+3k/4-3.$

For $n/2<k\leq2n/3$, consider the graph $K_{n}-C_{k}.$ \ Then $G$ is not
$k$-ordered hamiltonian since there is no hamiltonian cycle containing the
vertices of $C_{k}$ in order, and $\delta(G)=n-3.$

For $2n/3<k\leq n$, consider the graph $K_{n}-\left(  k/2\right)  K_{2}$,
where $k$ is even, and the vertices of the ''missing'' matching are labeled as
$x_{1},x_{2},...,x_{k}$ in the natural order. Then $G$ is not $k$-ordered
hamiltonian since there is no hamiltonian cycle containing $x_{1}%
,x_{2},...,x_{k}$ in order, and $\delta(G)=n-2.$

We can summarize the previous discussion as follows. \ Let $\delta(n,k)$ be
the smallest integer $m$ for which any graph of order $n$ with minimum degree
at least $m$ is $k$-ordered hamiltonian. \ We then have the following theorem.

\bigskip

\begin{theorem}
For positive integers $k,n$ with $3\leq k\leq n$ we have

(i) $\delta(n,k)=\left\lceil \frac{n}{2}\right\rceil +\left\lfloor \frac{k}%
{2}\right\rfloor -1$, \ for $k\leq(n+3)/11;$

(ii) $\delta(n,k)>\frac{n}{2}+\frac{k}{2}-2$, \ for $(n+3)/11<k\leq n/3;$

(iii) $\delta(n,k)\geq2k-2,$ for $n/3<k<2(n+2)/5;$

(iv) $\delta(n,k)=\left\lceil n/2+\frac{3k-9}{4}\right\rceil $, \ for
$2(n+2)/5\leq k\leq n/2;$

(v) $\delta(n,k)=n-2$, for $n/2<k\leq2n/3;$ and

(vi) $\delta(n,k)=n-1$, \ for $2n/3<k\leq n.$
\end{theorem}

\bigskip

Figure 1 indicates the relationship between the exact bounds known for
$\delta(n,k)$ and the bounds provided by the examples.

\bigskip\begin{figure}[th]
\setlength{\unitlength}{0.4mm}
\par
\begin{center}
\begin{picture}
(350,300)(0,0) \put(40,50){\line(1,0){310}} \put(50,40){\line(0,1){257}}
\put(355,50){$k$} \put(47,300){$\delta$} \put(195,30){$n/2$} \put
(245,30){$2n/3$} \put(145,30){$n/3$} \put(165,30){$2n/5$} \put(47,30){$0$}
\put(30,50){$0$} \put(30,170){$n/2$} \put(30,210){$2n/3$} \put(30,240){$5n/6$}
\put(30,260){$7n/8$} \put(40,290){$n$} \put(200,55){$.$} \put(200,60){$.$}
\put(200,65){$.$} \put(200,70){$.$} \put(200,75){$.$} \put(200,80){$.$}
\put(200,85){$.$} \put(200,90){$.$} \put(200,95){$.$} \put(200,100){$.$}
\put(200,105){$.$} \put(200,110){$.$} \put(200,115){$.$} \put(200,120){$.$}
\put(200,125){$.$} \put(200,130){$.$} \put(200,135){$.$} \put(200,140){$.$}
\put(200,145){$.$} \put(200,150){$.$} \put(200,155){$.$} \put(200,160){$.$}
\put(200,165){$.$} \put(200,170){$.$} \put(200,175){$.$} \put(200,180){$.$}
\put(200,185){$.$} \put(200,190){$.$} \put(200,195){$.$} \put(200,200){$.$}
\put(200,205){$.$} \put(200,210){$.$} \put(200,215){$.$} \put(200,220){$.$}
\put(200,225){$.$} \put(200,230){$.$} \put(200,235){$.$} \put(200,240){$.$}
\put(200,245){$.$} \put(200,250){$.$} \put(200,255){$.$} \put(200,260){$.$}
\put(200,265){$.$} \put(200,270){$.$} \put(200,275){$.$} \put(200,280){$.$}
\put(200,285){$.$} \put(250,55){$.$} \put(250,60){$.$} \put(250,65){$.$}
\put(250,70){$.$} \put(250,75){$.$} \put(250,80){$.$} \put(250,85){$.$}
\put(250,90){$.$} \put(250,95){$.$} \put(250,100){$.$} \put(250,105){$.$}
\put(250,110){$.$} \put(250,115){$.$} \put(250,120){$.$} \put(250,125){$.$}
\put(250,130){$.$} \put(250,135){$.$} \put(250,140){$.$} \put(250,145){$.$}
\put(250,150){$.$} \put(250,155){$.$} \put(250,160){$.$} \put(250,165){$.$}
\put(250,170){$.$} \put(250,175){$.$} \put(250,180){$.$} \put(250,185){$.$}
\put(250,190){$.$} \put(250,195){$.$} \put(250,200){$.$} \put(250,205){$.$}
\put(250,210){$.$} \put(250,215){$.$} \put(250,220){$.$} \put(250,225){$.$}
\put(250,230){$.$} \put(250,235){$.$} \put(250,240){$.$} \put(250,245){$.$}
\put(250,250){$.$} \put(250,255){$.$} \put(250,260){$.$} \put(250,265){$.$}
\put(250,270){$.$} \put(250,275){$.$} \put(250,280){$.$} \put(250,285){$.$}
\put(150,55){$.$} \put(150,60){$.$} \put(150,65){$.$} \put(150,70){$.$}
\put(150,75){$.$} \put(150,80){$.$} \put(150,85){$.$} \put(150,90){$.$}
\put(150,95){$.$} \put(150,100){$.$} \put(150,105){$.$} \put(150,110){$.$}
\put(150,115){$.$} \put(150,120){$.$} \put(150,125){$.$} \put(150,130){$.$}
\put(150,135){$.$} \put(150,140){$.$} \put(150,145){$.$} \put(150,150){$.$}
\put(150,155){$.$} \put(150,160){$.$} \put(150,165){$.$} \put(150,170){$.$}
\put(150,175){$.$} \put(150,180){$.$} \put(150,185){$.$} \put(150,190){$.$}
\put(150,195){$.$} \put(150,200){$.$} \put(150,205){$.$} \put(170,55){$.$}
\put(170,60){$.$} \put(170,65){$.$} \put(170,70){$.$} \put(170,75){$.$}
\put(170,80){$.$} \put(170,85){$.$} \put(170,90){$.$} \put(170,95){$.$}
\put(170,100){$.$} \put(170,105){$.$} \put(170,110){$.$} \put(170,115){$.$}
\put(170,120){$.$} \put(170,125){$.$} \put(170,130){$.$} \put(170,135){$.$}
\put(170,140){$.$} \put(170,145){$.$} \put(170,150){$.$} \put(170,155){$.$}
\put(170,160){$.$} \put(170,165){$.$} \put(170,170){$.$} \put(170,175){$.$}
\put(170,180){$.$} \put(170,185){$.$} \put(170,190){$.$} \put(170,195){$.$}
\put(170,200){$.$} \put(170,205){$.$} \put(170,210){$.$} \put(170,215){$.$}
\put(170,220){$.$} \put(170,225){$.$} \put(170,230){$.$} \put(170,235){$.$}
\thicklines\put(250,290){\line(1,0){100}} \put(200,289){\line(1,0){50}}
\put(50,170){\line(5,2){10}} \thinlines\put(170,241){\line(5,3){30}}
\put(150,210){\line(2,3){20}} \put(50,170){\line(5,2){100}} \put
(50,170){\line(5,3){150}} \put(150,0){Figure 1: Bounds for $\delta(n,k)$}
\end{picture}
\end{center}
\end{figure}

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\textbf{Bibliography}

\bigskip

[1]. G. Dirac, Some theorems on abstract graphs, \textit{Proc. London Math.
Soc. }2(1952), 69-81.

\bigskip

[2]. \ J. Faudree, R. Faudree, R. Gould, M. Jacobson, L.Lesniak, On
$k$-ordered graphs, \textit{J. Graph Theory}, to appear.

\bigskip

[3]. \ H. Kierstead, \ G. S\'{a}rk\"{o}zy, S. Selkow, On $k$-ordered
hamiltonian graphs, \textit{J. Graph Theory} 32(1999), 17-25.

\bigskip

[4]. L. Lov\'{a}sz and M.D. Plummer, \textit{Matching Theory}, Akad\'{e}miai
Kiad\'{o}, Budapest(1986).

\bigskip

[5]. \ L. Ng and M. Schultz, $k$-Ordered hamiltonian graphs, $\mathit{k}%
$-Ordered hamiltonian graphs, \textit{\ J. Graph Theory \ 2(1997), 45-57.}

\bigskip

[6]. O. Ore, Note on Hamilton circuits, \textit{Amer. Math. Monthly} 67(1960), 55.
\end{document}