Strong subgraph $k$-connectivity bounds

Abstract

Let $D=(V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and $2\le k\le n$. Strong subgraphs $D_1,\dots ,D_p$ containing $S$ are said to be internally disjoint if $V(D_i)\cap V(D_j)=S$ and $A(D_i)\cap A(D_j)=\varnothing$ for all $1\le i<j\le p$. Let ${\kappa }_S(D)$ be the maximum number of internally disjoint strong digraphs containing $S$ in $D$. The strong subgraph $k$-connectivity is defined as $${\kappa }_k(D)=\min \{{\kappa }_S(D)\mid S\subseteq V,|S|=k\}.$$ A digraph $D=(V,A)$ is called minimally strong subgraph $(k,\ell )$-connected if ${\kappa }_k(D)\ge \ell$ but for any arc $e\in A$, ${\kappa }_k(D-e)\le \ell -1$. In this paper, we first give a sharp upper bound for the parameter ${\kappa }_k(D)$ and then study the minimally strong subgraph $(k,\ell )$-connected digraphs.