Domination game : extremal families of graphs for the 3 / 5-conjectures
Domination game : extremal families of graphs for the 3 / 5-conjectures
复制标题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
B. Brešar
中科院分区：
文献类型：
--
作者：
B. Brešar
Two players, Dominator and Staller, alternate choosing vertices of a graph G, one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of the Dominator is to finish the game as soon as possible, while the aim of the Staller is just the opposite. The game domination number g(G) is the number of vertices chosen when Dominator starts the game and both players play optimally. It has been conjectured in [7] that g(G) ≤ 3∣V (G)∣ 5 holds for an arbitrary graph G with no isolated vertices, which is in particular open when G is a forest. In this paper we present constructions that lead to large families of trees that attain the conjectured 3/5-bound. Some of these families can be used to construct graphs with game domination number
