%% 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{}
%TCIDATA{}
\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/22n/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\frac{n}{2}+\frac{k}{2}-2$, \ for $(n+3)/11