On the spanning connectivity of tournaments

Abstract

Let $D$ be a digraph. A $k$-container of $D$ between $u$ and $v$, $C(u,v)$, is a set of $k$ internally disjoint paths between $u$ and $v$. A $k$-container $C(u,v)$ of $D$ is a strong (resp. weak) $k^{\ast }$-container if there is a set of $k$ internally disjoint paths with the same direction (resp. with different directions allowed) between $u$ and $v$ and it contains all vertices of $D$. A digraph $D$ is $k^{\ast }$-strongly (resp. $k^{\ast }$-weakly) connected if there exists a strong (resp. weak) $k^{\ast }$-container between any two distinct vertices. We define the strong (resp. weak) spanning connectivity of a digraph $D$, ${\kappa }_s^{\ast }(D)$ (resp. ${\kappa }_w^{\ast }(D)$ ), to be the largest integer $k$ such that $D$ is ${\omega }^{\ast }$-strongly (resp. ${\omega }^{\ast }$-weakly) connected for all $1\le \omega \le k$ if $D$ is a $1^{\ast }$-strongly (resp. $1^{\ast }$-weakly) connected. In this paper, we show that a tournament with $n$ vertices and irregularity $i(T)\le k$, if $n\ge 6t+5k$ $(t\ge 2)$, then ${\kappa }_s^{\ast }(T)\ge t$ and ${\kappa }_w^{\ast }(T)\ge t+1$ if $n\ge 6t+5k-3$ $(t\ge 2)$.

11 pages