Domination game

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

Povzetek

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.

Ključne besede

teorija grafov;teorija iger;dominantnost;Vizingova domneva;graph theory;game theory;domination;domination game;game domination number;Vizing's conjecture;

Podatki

Jezik:	Angleški jezik
Leto izida:	2009
Tipologija:	0 - Ni določena
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17:519.83
COBISS:	15032921
ISSN:	1318-4865
Št. ogledov:	1016
Št. prenosov:	17
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarne ključne besede:	teorija grafov;teorija iger;dominantnost;Vizingova domneva;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1-14
Letnik:	ǂVol. ǂ47
Zvezek:	ǂšt. ǂ1066
Čas izdaje:	2009
ID:	1474075