How Long Can One Bluff in the Domination Game?

• Autorzy: Boštan Brešar , Paul Dorbec , Sandi Klavžar , Gašpar Košmrlj
• Języki publikacji: EN

Abstrakty

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.

Słowa kluczowe

EN

domination game; game domination number; bluff graphs; minus graphs; generalized Petersen graphs; Kneser graphs; Cartesian product of graphs; Hamming graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 2
• Strony: 337-352

Daty

wydano

2017-05-01

otrzymano

2015-10-19

zaakceptowano

2016-01-07

online

2017-04-01

Twórcy

autor

Boštan Brešar

• Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana,

autor

Paul Dorbec

• Univ. Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France CNRS, LaBRI, UMR 5800, F-33400 Talence,

autor

Sandi Klavžar

• Faculty of Mathematics and Physics, University of Ljubljana, Slovenia Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana,

autor

Gašpar Košmrlj

• Institute of Mathematics, Physics and Mechanics, Ljubljana,

Identyfikatory

DOI

10.7151/dmgt.1899