pith. sign in

arxiv: 1706.04742 · v1 · pith:PPGZZHTMnew · submitted 2017-06-15 · 🧮 math.CO

On the spanning connectivity of tournaments

classification 🧮 math.CO
keywords respcontainerkappaconnecteddigraphomegastrongstrongly
0
0 comments X
read the original 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^{*}$-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^{*}$-strongly (resp. $k^{*}$-weakly) connected if there exists a strong (resp. weak) $k^{*}$-container between any two distinct vertices. We define the strong (resp. weak) spanning connectivity of a digraph $D$, $\kappa_{s}^{*}(D)$ (resp. $\kappa_{w}^{*}(D)$ ), to be the largest integer $k$ such that $D$ is $\omega^{*}$-strongly (resp. $\omega^{*}$-weakly) connected for all $1\leq \omega\leq k$ if $D$ is a $1^{*}$-strongly (resp. $1^{*}$-weakly) connected. In this paper, we show that a tournament with $n$ vertices and irregularity $i(T)\leq k$, if $n\geq6t+5k$ $(t\geq2)$, then $\kappa_{s}^{*}(T)\geq t$ and $\kappa_{w}^{*}(T)\geq t+1$ if $n\geq6t+5k-3$ $(t\geq2)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.