Article ID Journal Published Year Pages File Type
6871387 Discrete Applied Mathematics 2018 5 Pages PDF
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
, , ,