با سلام خدمت کاربران در صورتی که با خطای سیستم پرداخت بانکی مواجه شدید از طریق کارت به کارت (6037997535328901 بانک ملی ناصر خنجری ) مقاله خود را دریافت کنید (تا مشکل رفع گردد).
دسته بندی:
علوم کامپیوتر - computer science
سال انتشار:
2013
ترجمه فارسی عنوان مقاله:
بازی سلطه که روی درخت و زیرگراف های پوشا انجام می شود
عنوان انگلیسی مقاله:
Domination game played on trees and spanning subgraphs
منبع:
Sciencedirect - Elsevier - Discrete Mathematics 313 (2013) 915–923
نویسنده:
Boštjan Brešar, Sandi Klavžar, Douglas F. Rall
چکیده انگلیسی:
The domination game, played on a graph G, was introduced in Brešar et al. (2010) [2].
Vertices are chosen, one at a time, by two players Dominator and Staller. Each chosen vertex
must enlarge the set of vertices of G dominated to that point in the game. Both players
use an optimal strategy—Dominator plays so as to end the game as quickly as possible,
and Staller plays in such a way that the game lasts as many steps as possible. The game
domination number γg (G) is the number of vertices chosen when Dominator starts the
game and the Staller-start game domination number γ ′
g (G) is the result when Staller starts
the game.
In this paper these two games are studied when played on trees and spanning subgraphs.
A lower bound for the game domination number of a tree in terms of the order and
maximum degree is proved and shown to be asymptotically tight. It is shown that for every
k, there is a tree T with (γg (T ), γ ′
g (T )) = (k, k+1) and conjectured that there is none with
(γg (T ), γ ′
g (T )) = (k, k − 1). A relation between the game domination number of a graph
and its spanning subgraphs is considered. It is proved that there exist 3-connected graphs
G having a 2-connected spanning subgraph H such that the game domination number of H
is arbitrarily smaller than that of G. Similarly, for any integer ℓ ≥ 1, there exists a graph G
and a spanning tree T such that γg (G)−γg (T ) ≥ ℓ. On the other hand, there exist graphs G
such that the game domination number of any spanning tree of G is arbitrarily larger than
that of G.
Keywords: Domination game | Game domination number | Tree | Spanning subgraph
چکیده فارسی:
بازی سلطه که روی گراف G بازی می شود توسط برسار و همکاران در سال 2010 معرفی شد [2]. هر زمان یک رأس با دو بازیکن دومینیتور و استالر انتخاب شده اند. هر رأس انتخابی باید مجموعه ی رأس های G تحت سلطه ی یک نقطه در بازی را بزرگ کند. هر دو بازیکن از یک استراتژی بهینه استفاده می کنند و دومینیتور به همین ترتیب تا انتها بازی می کند و سعی می کند با سرعت بالا انجام شود و استالر باید به گونه ای بازی کند که بازی بیشتر طول بکشد.
تعداد سلطه ی بازی تعداد رأس هایی است که زمانی که بازی سلطه آغاز می شود انتخاب می شوند و تعداد سلطه ی بازی staller-start نتیجه ای است که با آغاز بازی توسط استالر انجام می شود.
در این مقاله دو بازی زمانی که روی درخت ها و زیرگراف های پوشا بازی می شوند مورد مطالعه قرار گرفته اند. حد پایین تعداد بازی تسلط درخت از نظر درجه ی ماکزیمم و مرتبه ارائه شده است و از نظر مجانبی محدود است. نشان داده شده است که برای هر K، یک درخت T با وجود دارد و حدس زده می شود که هیچ چیزی با رابطه ی وجود ندارد. رابطه ی بین تعداد سلطه ی بازی گراف و زیرگراف های آن در نظر گرفته شده اند. ثابت شده است که گراف های 2-همبند وجود دارد و G زیرگراف پوشای 2-همبند به نام H دارد که تعداد سلطه ی بازی H یک مقدار کوچکتر از G است. به طور مشابه برای هر عدد صحیح، ، یک گراف G و یک زیردرخت T وجود دارد به گونه ای که داریم . از سوی دیگر، گراف G وجود دارد به گونه ای که تعداد سلطه ی هر درخت پوشای G بزرگتر از G است.
کلمات کلیدی: بازی سلطه | تعداد بازی سلطه | درخت | زیر گراف پوشا
حجم فایل: 588 کیلوبایت
قیمت: 25200 تومان
توضیحات اضافی:
تعداد نظرات : 0