Cyclic Neighborhoods in Digraphs

Abstract

Let $D$ be a digraph of order $n$ and size $m$ with the property that no out-neighborhood or in-neighborhood of any vertex is acyclic. We show that, if $D$ is strongly connected, then $m\ge 7n/3$, and, if $D$ is strongly $2$-connected, then $m\ge 8n/3$. Both results are best-possible.