Extremal Problems for the Family of $k$-Strongly Connected Digraphs

Abstract

Let $\mathcal{D}$ be a family of digraphs. A digraph $D$ is \emph{$\mathcal{D}$-saturated} if it contains no member of $\mathcal{D}$ as a subdigraph, but for any arc $e$ in the complement of $D$, the digraph $D+e$ contains some member of $\mathcal{D}$ as a subdigraph. The \emph{saturation number} $\mathrm{sat}(n,\mathcal{D})$ and the \emph{extremal number} $\mathrm{ex}(n,\mathcal{D})$ are the minimum number and the maximum number of arcs among all $n$-vertex $\mathcal{D}$-saturated digraphs. For a positive integer $k$, let ${\mathcal{D}}_k$ denote the family of \emph{$k$-strongly connected digraphs}. In this paper, firstly, we prove that $$\mathrm{sat}(n,{\mathcal{D}}_k)=(k-1)(2n-k)+\left(\genfrac{}{}{0ex}{}{n-k+1}{2}\right).$$ Then for $n\ge 3(k-1)$, we prove that $$\mathrm{ex}(n,{\mathcal{D}}_k)\le \left(\genfrac{}{}{0ex}{}{n-k+1}{2}\right)+\frac{17}{6}(k-1)(n-k+1).$$ In addition, we conjecture that for sufficiently large $n$, $$\mathrm{ex}(n,{\mathcal{D}}_k)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\frac{3}{2}(k-\frac{4}{3})(n-k+1).$$