کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903865 1632963 2018 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Domination in tournaments
ترجمه فارسی عنوان
تسلط در مسابقات
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We investigate the following conjecture of Hehui Wu: for every tournament S, the class of S-free tournaments has bounded domination number. We show that the conjecture is false in general, but true when S is 2-colourable (that is, its vertex set can be partitioned into two transitive sets); the latter follows by a direct application of VC-dimension. Our goal is to go beyond this; we give a non-2-colourable tournament S that satisfies the conjecture. The key ingredient here (perhaps more interesting than the result itself) is that we overcome the unboundedness of the VC-dimension by showing that the set of shattered sets is sparse.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 130, May 2018, Pages 98-113
نویسندگان
, , , , ,