کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949612 | 1440197 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Infinite quasi-transitive digraphs with domination number 2
ترجمه فارسی عنوان
ارجاعات نامتقارن شبه ترانزیتی با سلطه شماره 2
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In 2014 D. Pálvölgyi and A. Gyárfás explored the minimum dominating set of a digraph with an arc partition into transitive digraphs. A. Gyárfás proposed the conjecture “for each positive integer
k, there exists a (least)
p(k) such that every
k-transitive tournament has a dominating set of at most
p(k) vertices” a special case of a conjecture of ErdÅs, Sands, Sauer and Woodrow, and they show its relations with other conjectures as well as important consequences in case the conjecture is true. We consider the vertex version of this problem and prove that a finite or infinite quasi-transitive digraph with no infinite inward paths and a vertex partition into k-transitive tournaments has a dominating set of order at most two, if the vertex partition has at most two infinite classes, no heterochromatic directed triangles and δâ(Dâ²)â¥1, for every induced digraph Dâ² on three classes of the vertex partition. This result also holds for tournaments, which are quasi-transitive digraphs. Finally, we show that the conditions are tight.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 44-50
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 44-50
نویسندگان
Hortensia Galeana-Sánchez, Mika Olsen,