Domination game
Abstract
The domination game played on a graph ▫$G$▫ consists of two players, Dominator and Staller who alternate taking turns choosing a vertex from ▫$G$▫ such that whenever a vertex is chosen the graph in as few steps as possible and Staller wishes to delay the process as much as possible. The game domination number ▫$\gamma_g(G)$▫ is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number ▫$\gamma'_g(G)$▫ when Staller starts the game. It is proved that for any graph ▫$G$▫, ▫$\gamma(G) \le \gamma_g(G) \le 2\gamma(G) - 1$▫, and that all possible values can be realized. It is also proved that for any graph ▫$G$▫, ▫$\gamma_g(G) - 1 \le \gamma'_g(G) \le \gamma_g(G) + 2$▫, and that most of the possibilities for mutual values of ▫$\gamma_g(G)$▫ and ▫$\gamma'_g(G)$▫ can be realized. A connection with Vizing's conjecture is established and several problems and conjectures stated.
Keywords
teorija grafov;teorija iger;dominantnost;Vizingova domneva;graph theory;game theory;domination;domination game;game domination number;Vizing's conjecture;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2009 |
| Typology: | 0 - Not set |
| Organization: | UL FMF - Faculty of Mathematics and Physics |
| UDC: | 519.17:519.83 |
| COBISS: |
15032921
|
| ISSN: | 1318-4865 |
| Views: | 1016 |
| Downloads: | 17 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | Unknown |
|---|---|
| Secondary keywords: | teorija grafov;teorija iger;dominantnost;Vizingova domneva; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Not categorized |
| Pages: | str. 1-14 |
| Volume: | ǂVol. ǂ47 |
| Issue: | ǂšt. ǂ1066 |
| Chronology: | 2009 |
| ID: | 1474075 |
Recommended works:
Domination game
2009,
no subtitle data available
Domination game: extremal families of graphs for 3/5-conjectures
2013,
no subtitle data available
Fair reception and Vizing's conjecture
2009,
no subtitle data available
Vizing's conjecture: a survey and recent results
2009,
no subtitle data available
Vizing's conjecture: a survey and recent results
2012,
no subtitle data available