کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646529 1632250 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cycles and transitivity by monochromatic paths in arc-coloured digraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Cycles and transitivity by monochromatic paths in arc-coloured digraphs
چکیده انگلیسی

A digraph DD is an mm-coloured digraph   if its arcs are coloured with mm colours. If DD is an mm-coloured digraph and a∈A(D)a∈A(D), then colour(a)colour(a) will denote the colour   has been used on aa. A path (or a cycle) is monochromatic   if all of its arcs are coloured alike. A set N⊆V(D)N⊆V(D) is a kernel by monochromatic paths   if it satisfies the following two conditions: (i) for every pair of different vertices u,v∈Nu,v∈N there is no monochromatic path between them and; (ii) for every vertex x∈V(D)∖Nx∈V(D)∖N there is a vertex y∈Ny∈N such that there is an xyxy-monochromatic path.The closure   of DD, denoted by C(D)C(D), is the mm-coloured multidigraph defined as follows: V(C(D))=V(D)V(C(D))=V(D), A(C(D))=A(D)∪{(u,v)A(C(D))=A(D)∪{(u,v) with colour i|i| there is an uvuv-path coloured ii contained in D}D}. A subdigraph HH in DD is rainbow   if all of its arcs have different colours. A digraph DD is transitive by monochromatic paths   if the existence of an xyxy-monochromatic path and an yzyz-monochromatic path in DD imply that there is an xzxz-monochromatic path in DD. We will denote by P3⃗ the path of length   3 and by C3⃗ the cycle of length 3.Let DD be a finite mm-coloured digraph. Suppose that CC is the set of colours used in A(D)A(D), and ζ={C1,C2,…,Ck}ζ={C1,C2,…,Ck} (k≥2k≥2) is a partition of CC, such that for every i∈{1,2,…,k}i∈{1,2,…,k} happens that Hi=D[{a∈A(D)∣colour(a)∈Ci}]Hi=D[{a∈A(D)∣colour(a)∈Ci}] is transitive by monochromatic paths. Let {ζ1,ζ2}{ζ1,ζ2} be a partition of ζζ, and DiDi will be the spanning subdigraph of DD such that A(Di)={a∈A(D)∣colour(a)∈CjforsomeCj∈ζi}. In this paper, we give some sufficient conditions for the existence of a kernel by monochromatic paths in a digraph with the structure mentioned above. In particular we obtain extensions of the following two original results:The result by Sands et al. (1982) that asserts: Every 2-coloured digraph has a kernel by monochromatic paths, and the result by Galeana-Sánchez et al. (2011) that asserts: If DD is a finite mm-coloured digraph that admits a partition {C1,C2}{C1,C2} of the set of colours of DD such that for each i∈{1,2}i∈{1,2} every cycle in the subdigraph D[Ci]D[Ci] spanned by the arcs with colours in CiCi is monochromatic, C(D)C(D) does not contain neither rainbow triangles nor rainbow P3⃗ (path of length   3) involving colours of both C1C1 and C2C2; then DD has a kernel by monochromatic paths.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 12, Issues 2–3, November–December 2015, Pages 104–112
نویسندگان
, , ,