Boštjan Brešar (Author), Sandi Klavžar (Author), Douglas F. Rall (Author)

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:
Typology: 0 - Not set
Organization: UL FMF - Faculty of Mathematics and Physics
UDC: 519.17:519.83
COBISS: 15032921 Link will open in a new window
ISSN: 1318-4865
Views: 1016
Downloads: 17
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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:
, no subtitle data available
, no subtitle data available
, no subtitle data available
, no subtitle data available
, doktorska disertacija