مقاله ترجمه شده درباره تسلط در 3-تورنمنت ها – سال 2017
مشخصات مقاله:
عنوان فارسی مقاله:
تسلط در 3-تورنمنت ها
عنوان انگلیسی مقاله:
Domination in 3-tournaments
مناسب برای رشته های دانشگاهی زیر:
ریاضی
مناسب برای گرایش های دانشگاهی زیر:
ریاضی محض
وضعیت مقاله انگلیسی و ترجمه:
مقاله انگلیسی را میتوانید به صورت رایگان با فرمت PDF از باکس زیر دانلود نمایید. ترجمه این مقاله با فرمت WORD – DOC آماده خریداری و دانلود آنی میباشد.
فهرست مطالب:
چکیده
حدس 1 (جیارفاس)
تذکرها
قسمتی از مقاله انگلیسی و ترجمه آن:
Conjecture 1 (Gyárfás)
There are 3-tournaments with arbitrarily large domination number. 2. The domination number of a 3-tournament such that any four of its vertices induce at least two edges with the same tail is bounded by a constant. These conjectures were motivated by analogous classic results about usual tournaments (see, e.g., [7]). Indeed, it is well known that an n-vertex tournament can have a domination number as large as (1 + o(1))log2 n, e.g., random tournaments have this property. On the other hand, if any three vertices of a tournament induce two edges with the same tail, i.e., there are no cyclic triangles, then the tournament is transitive and thus has a dominating set of size 1. In this short note we construct 3-tournaments of arbitrarily large domination number such that any four vertices induce at least two edges with the same tail. This proves the first conjecture and disproves the second.
حدس 1 (جیارفاس).
3-تورنمنت ها با عدد تسلطی بزرگ به طور دلخواه وجود دارند.
عدد تسلطی از یک 3-تورنمنت، که هر چهار رأسش حداقل دو یال با دنباله یکسان ایجاد می کند، کراندار با یک عدد ثابت است.
انگیزه برای این حدس ها به وسیله نتایج کلاسیک مشابه درباره تورنمنت های مهمولی ایجاد شده است (برای مثال [7] را ببینید). بوضوح، بخوبی شناخته شده است که یک تورنمنت n – رأسی می تواند یک عدد تسلطی به بزرگی (1 + o(1)) 〖log〗_2 n داشته باشد، مثلا، تورنمنت های تصادفی این ویژگی را دارند. از طرف دیگر، اگر هر سه رأس از یک تورنمنت، دو یال با دنباله یکسان ایجاد کنند، یعنی، هیچ دور مثلثی وجود نداشته باشد، آنگاه تورنمنت تعدی است و بنابراین یک مجموعه تسلطی از اندازه 1 دارد.
در این یادداشت کوتاه، 3-تورنمنت ها از عدد تسلطی بزرگ دلخواه می سازیم بطوریکه هر چهار رأس حداقل دو یال با دنباله یکسان ایجاد می کنند. این مطلب، حدس نخست را اثبات کرده و دومی را رد می کند.
