PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 2 | 369-381
Tytuł artykułu

Domination Game: Extremal Families for the 3/5-Conjecture for Forests

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107] posted their 3/5-Conjecture that γg(G) ≤ ⅗n for every isolate-free forest on n vertices. Brešar, Klavžar, Košmrlj and Rall [Discrete Appl. Math. 161 (2013) 1308-1316] presented a construction that yields an infinite family of trees that attain the conjectured 3/5-bound. In this paper, we provide a much larger, but simpler, construction of extremal trees. We conjecture that if G is an isolate-free forest on n vertices satisfying γg(G) = ⅗n, then every component of G belongs to our construction.
Słowa kluczowe
Wydawca
Rocznik
Tom
37
Numer
2
Strony
369-381
Opis fizyczny
Daty
wydano
2017-05-01
otrzymano
2015-10-21
poprawiono
2016-04-30
zaakceptowano
2016-04-30
online
2017-04-01
Twórcy
  • Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006,, mahenning@uj.ac.za
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1931
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.