Guarded subgraphs and the domination game

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

Abstract

V članku vpeljemo koncept zaščitenega podgrafa. Množica le-teh po definicji leži med množico konveksnih in 2-izometričnih podgrafov, hkrati pa ni primerljiva z množico izometričnimih podgrafov. Dokažemo nekatere metrične lastnosti zaščitenih podgrafov ter koncept uporabimo v dominacijski igri, v kateri dva igralca, Dominator in Zavlačevalka, izmenično izbirata vozlišča grafa, tako da vsako izbrano vozlišče poveča množico dominiranih vozlišč. Dominatorjev cilj je končati igro, tj. dominirati celoten graf, čim hitreje, medtem ko je Zavlačevalkin cilj odigrati čim več potez. Igralno dominacijsko število je število potez v igri, ko Dominator začne in oba igralca igrata optimalno. Kot glavni rezultat članka dokažemo, da igralno dominacijsko število grafa ni nikoli manjše, kot igralno dominacijsko število njegovega zaščitenega podgrafa. Predstavljenih je tudi več aplikacij tega rezultata.

Keywords

dominacijska igra;igralno dominacijsko številko;konveksni podgraf;(2-)izometrični podgraf;domination game;game domination number;convex subgraph;(2-)isometric subgraph;

Data

Language:	English
Year of publishing:	2015
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	17273689
ISSN:	1365-8050
Views:	0
Downloads:	0
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Zaščiteni podgrafi in dominacijska igra
Secondary abstract:	We introduce the concept of guarded subgraph of a graph, which as a condition lies between convex and 2-isometric subgraphs and is not comparable to isometric subgraphs. Some basic metric properties of guarded subgraphs are obtained, and then this concept is applied to the domination game. In this game two players, Dominator and Staller, alternate choosing vertices of a graph, one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of Dominator is that the graph is dominated in as few steps as possible, while the aim of Staller is just the opposite. The game domination number is the number of vertices chosen when Dominator starts the game and both players play optimally. The main result of this paper is that the game domination number of a graph is not smaller than the game domination number of any guarded subgraph. Several applications of this result are presented.
Secondary keywords:	domination game;game domination number;convex subgraph;(2-)isometric subgraph;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 161-168
Volume:	ǂVol. ǂ17
Issue:	ǂno. ǂ1
Chronology:	2015
ID:	9142040