کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646942 1342320 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Domination game on forests
ترجمه فارسی عنوان
بازی تسلط بر روی جنگل ها
کلمات کلیدی
بازی تسلط، شماره سلطه بازی، 3/5-حدس
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

In the domination game studied here, Dominator and Staller alternately choose a vertex of a graph GG and take it into a set DD. The number of vertices dominated by the set DD must increase with each move and the game ends when DD becomes a dominating set of GG. Dominator aims to minimize while Staller aims to maximize the number of turns (or equivalently, the size of the dominating set DD obtained at the end). Assuming that Dominator starts and both players play optimally, the number of turns is the game domination number  γg(G)γg(G) of GG.Kinnersley, West, and Zamani proved that γg(G)≤7n/11γg(G)≤7n/11 for every isolate-free nn-vertex forest GG, and they conjectured that the sharp upper bound is only 3n/53n/5. Here, we prove the 3/5-conjecture for forests in which no two leaves are at distance 4 apart. Further, we establish an upper bound γg(G)≤5n/8γg(G)≤5n/8 for every nn-vertex isolate-free forest GG.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2220–2228
نویسندگان
,