کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648052 1342391 2011 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kernels by monochromatic paths in digraphs with covering number 2
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Kernels by monochromatic paths in digraphs with covering number 2
چکیده انگلیسی

We call the digraph DD an kk-colored digraph if the arcs of DD are colored with kk colors. A subdigraph HH of DD is called monochromatic if all of its arcs are colored alike. A set N⊆V(D)N⊆V(D) is said to be 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 directed path between them, and (ii) for every vertex x∈(V(D)∖N)x∈(V(D)∖N), there is a vertex y∈Ny∈N such that there is an xyxy-monochromatic directed path. In this paper, we prove that if DD is an kk-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,43,4 or 55 is monochromatic, then DD has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural number  llsuch that if a digraph  DDis  kk-colored so that every directed cycle of length at most  llis monochromatic, then  DDhas a kernel by monochromatic paths?

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 13, 6 July 2011, Pages 1111–1118
نویسندگان
, ,