کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871225 1440180 2018 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Rainbow connections in digraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Rainbow connections in digraphs
چکیده انگلیسی
In this paper, we study the rainbow connection, rainbow vertex-connection and total rainbow connection numbers of digraphs. We give some properties of these parameters and establish relations between them. The rainbow connection number and the rainbow vertex-connection number of a digraph D are both upper bounded by the order of D, while its total rainbow connection number is upper bounded by twice of its order. In particular, we prove that a digraph of order n has rainbow connection number n if and only if it is Hamiltonian and has three vertices with eccentricity n−1, that it has rainbow vertex-connection number n if and only if it has a Hamiltonian cycle C and three vertices with eccentricity n−1 such that no two of them are consecutive on C, and that it has total rainbow connection number 2n if and only if it has rainbow vertex-connection number n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 243, 10 July 2018, Pages 248-261
نویسندگان
, ,