کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871387 1440184 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the spanning connectivity of tournaments
ترجمه فارسی عنوان
در اتصال به مسابقات
کلمات کلیدی
مسیر همیلتون اتصال پیوستن اتصال، میان بر، مسابقات،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 239, 20 April 2018, Pages 218-222
نویسندگان
, , ,