Guarded subgraphs and the domination gameBrešar, Boštjan (Avtor) Klavžar, Sandi (Avtor) Košmrlj, Gašper (Avtor) Rall, Douglas F. (Avtor) dominacijska igraigralno dominacijsko številkokonveksni podgraf(2-)izometrični podgrafV č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.Discrete Mathematics & Theoretical Computer Science 20152016-05-11 03:52:54Znanstveno delo59258ISSN: 1365-8050UDK: 519.17OceCobissID: 8089433COBISS_ID: 17273689ISSN pri članku: 1365-8050NUK URN: URN:SI:UM:DK:B52WXJ2Dsl