\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Marietjie Frick, Susan A van Aardt, Jean E Dunbar, Morten H Nielsen and Ortrud R Oellermann}
%
%
\medskip
\noindent
%
%
{\bf A Traceability Conjecture for Oriented Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
A (di)graph $G$ of order $n$ is $k$-traceable (for some $k$, $1\leq
k\leq n$) if every induced sub(di)graph of $G$ of order $k$ is
traceable. \ It follows from Dirac's degree condition for
hamiltonicity that for $k\geq2$ every $k$-traceable graph of order at
least $2k-1$ is hamiltonian. The same is true for strong oriented
graphs when $k=2,3,4,$ but not when $k\geq5$. However, we conjecture
that for $k\geq2$ every $k$-traceable oriented graph of order at least
$2k-1$ is traceable.  The truth of this conjecture would imply the
truth of an important special case of the Path Partition Conjecture
for Oriented Graphs. In this paper we show the conjecture is true for
$k \leq 5$ and for certain classes of graphs.  In addition we show
that every strong $k$-traceable oriented graph of order at least
$6k-20$ is traceable. We also characterize those graphs for which all
walkable orientations are $k$-traceable.

\bye

.
