Wyniki wyszukiwania

1

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

100%

Henning M. A., Löwenstein C.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 2

369-381

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.

2

Domination Game Critical Graphs

70%

Bujtás C., Klavžar S., Košmrlj G.

Discussiones Mathematicae Graph Theory

|

2015

|

tom 35

|

nr 4

781-796

EN

The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γg(G), named the game domination number. Here we study the γg-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize γg-critical graphs with γg = 2 and with γg = 3, moreover for each n we identify the (infinite) class of all γg-critical ones among the nth powers CnN of cycles. Along the way we determine γg(CnN) for all n and N. Results of a computer search for γg-critical trees are presented and several problems and research directions are also listed.

3

How Long Can One Bluff in the Domination Game?

51%

Brešar B., Dorbec P., Klavžar S., Košmrlj G.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 2

337-352

EN

The domination game is played on an arbitrary graph G by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs K(n, 2), n ≥ 6, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

2 Klavžar S.

2 Košmrlj G.

1 Brešar B.

1 Bujtás C.

1 Dorbec P.

1 Henning M. A.

1 Löwenstein C.

2 2017

1 2015

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

Domination Game Critical Graphs

How Long Can One Bluff in the Domination Game?