Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871387 | Discrete Applied Mathematics | 2018 | 5 Pages |
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 (kâ¥2) 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 for kâ¥2. Specially, we define D is 1â-connected if D is weakly Hamiltonian connected (a 1â-connected digraph is 1â-strongly and also 1â-weakly connected.) We define the strong (resp. weak) spanning connectivity of a digraph D, κsâ(D) (resp. κwâ(D) ), to be the largest integer k such that D is Ïâ-strongly (resp. Ïâ-weakly) connected for all 1â¤Ïâ¤k. In this paper, we show that for kâ¥0, a (2k+1)-strong tournament is (k+2)â-weakly connected and that for kâ¥2, a 2k-strong tournament is kâ-strongly connected. Furthermore, we show that in a tournament with n vertices and irregularity i(T)â¤k, if nâ¥6t+5k(tâ¥2), then κsâ(T)â¥t and if nâ¥6t+5kâ3(tâ¥2), then κwâ(T)â¥t+1.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bo Zhang, Weihua Yang, Shurong Zhang,