\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf Jian Shen}
%
%
\medskip
\noindent
%
%
{\bf Short Cycles in Digraphs with Local Average Outdegree at Least Two}
%
%
\vskip 5mm
\noindent
%
%
%
%
Suppose $G$ is a strongly connected digraph with order $n$ girth
$g$ and diameter $d$. We prove that $d +g \le n$ if $G$ contains
no arcs $(u,v)$ with $\deg^+(u)=1$ and $\deg^+(v) \le 2$.

Caccetta and H${\rm\ddot{a}}$ggkvist showed in 1978
that any digraph of order $n$ with minimum outdegree $2$ contains
a cycle of length at most $\lceil n/2 \rceil$. Applying the
above-mentioned result, we improve their result by replacing  the
minimum outdegree condition by some weaker conditions involving
the local average outdegree. In particular, we prove that, for any
digraph $G$ of order $n$, if either

\smallskip

\item{(1)} $G$ has minimum outdegree $1$ and
$\deg^+(u) +\deg^+(v) \ge 4$ for all
arcs $(u,v)$, or

\item{(2)} $\deg^+(u) +\deg^+(v) \ge 3$ for all pairs 
of distinct vertices $u,v$,

\smallskip

\noindent then $G$ contains a cycle of length at most $\lceil n/2 \rceil$.



\bye

.