20.500.12556/DKUM-59258 Guarded subgraphs and the domination game Zaščiteni podgrafi in dominacijska igra 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. 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. dominacijska igra igralno dominacijsko številko konveksni podgraf (2-)izometrični podgraf domination game game domination number convex subgraph (2-)isometric subgraph true true true Discrete Mathematics & Theoretical Computer Science Angleški jezik Slovenski jezik Znanstveno delo 2016-05-11 03:52:54 2017-07-10 11:28:55 2025-09-24 11:09:32 2019-07-11 11:08:00 2015 0 0 Str. 161-168 št. 1 Letn. 17 2015 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 2014-06-08 2015-02-12 1365-8050 519.17 8089433 17273689 1365-8050 URN:SI:UM:DK:B52WXJ2D Discrete_Mathematics_&_Theoretical_Computer_Science_2015_Bresar_et_al._Guarded_subgraphs_and_the_domination_game.pdf Discrete_Mathematics_&_Theoretical_Computer_Science_2015_Bresar_et_al._Guarded_subgraphs_and_the_domination_game.pdf 1 644B1ECC1DD7E3BDDE818323DE99332E 065c8b7088d7a69fd0403c6ffea1d22784351f64ee536b59fbc8bb3522b88557 6354f11c-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=113948 http://dmtcs.episciences.org/2123 1 https://dk.um.si/Dokument.php?lang=slv&id=91327 Fakulteta za naravoslovje in matematiko 0 0 0