i i \Irsic" | 2021/12/13 | 9:14 | page 141 | #1 i i i i i i Domination Games Played on Graphs B. Bre sar, M. A. Henning, S. Klav zar in D. F. Rall, Domination Games Played on Graphs, SpringerBriefs in Mathematics, Springer, Cham, 2021, 121 strani. Aprila je pri zalo zbi Springer iz sla nova knjiga z naslovom Domination Games Played on Graphs (Dominacijske igre na grah). Avtorji monograje so Bo stjan Bre sar (Univerza v Mariboru), Michael A. Henning (Univerza v Johannesburgu), Sandi Klav zar (Univerza v Ljubljani) in Douglas F. Rall (Univerza Furman), ki vsi sodijo med vodilne raziskovalce na podro cju dominacijskih iger. Knjiga predstavlja strnjen pregled razli cic do- minacijske igre ter rezultatov in odprtih problemov povezanih z njimi. V glav- nem je namenjena raziskovalcem, tako mladim kot izku senim. Avtorji v knjigi najve c pozornosti posvetijo osnovni raz- li cici dominacijske igre, ki je bila v zadnjem desetletju dele zna izjemne po- zornosti. Knjiga je razdeljena na pet poglavij. V prvem, uvodnem poglavju naj- demo potrebne oznake in denicije. Spomnimo se, da vozli s ce dominira sebe in svoje sosede. Podmno zica vozli s c grafa je dominacijska mno zica, ce dominira vsa vozli s ca grafa. Velikost najmanj se dominacijske mno zice je grafovska invarianta imenovana dominantno stevilo grafa G in ozna cena z (G). Dolo canje dominantnega stevila splo snih grafov je zahteven problem, zato je zanimivo nanj pogledati tudi z vidika teorije iger. Dominacijska igra je tekmovalna optimizacijska igra, ki so jo leta 2010 vpeljali prav Bre sar, Klav zar in Rall. Igro na danem grafu G igrata dva igralca (Dominator in Za- vla cevalka), ki izmeni cno izbirata vozli s ca in jih dodajata v izbrano mno zico. Vsako izbrano vozli s ce mora dominirati vsaj eno vozli s ce, ki ga prej izbrana vozli s ca ne dominirajo. Igra se kon ca, ko izbrana mno zica tvori dominacij- sko mno zico grafa G (in torej nadaljnje poteze niso mogo ce). Igralca imata nasprotujo ca si cilja: Dominator zeli dose ci cim manj so kon cno velikost iz- brane mno zice, Zavla cevalka pa te zi k cim ve cji kon cni mno zici izbranih Obzornik mat. fiz.68 (2021) 4 141 i i \Irsic" | 2021/12/13 | 9:14 | page 142 | #2 i i i i i i Nove knjige vozli s c. Igra nima zmagovalca ali pora zenca. Oba igralca preprosto sledita strategiji, ki najbolj ustreza njunemu cilju. Ce oba igrata optimalno, kon cna velikost mno zice izbranih vozli s c postane grafovska invarianta. Imenujemo jo igralno dominantno stevilo grafa G in ozna cimo z g (G), ce prvo potezo naredi Dominator, in z 0 g (G), ce je Zavla cevalka prva na potezi. Izmed razli cic dominacijske igre v prvem poglavju natan cneje spoznamo se celotno dominacijsko igro. Spomnimo se, da vozli s ce celotno dominira svoje sosede, ne pa tudi samega sebe. Celotna dominacijska igra je deni- rana podobno kot dominacijska igra, le da mora izbrano vozli s ce na vsaki potezi celotno dominirati vsaj eno vozli s ce, ki ga prej izbrana vozli s ca se ne dominirajo celotno. Ce oba igralca igrata optimalno in igro na grafu G za cne Dominator, dobljeno invarianto ozna cimo z tg (G). Drugo poglavje je posve ceno dominacijski igri. Predstavljena sta nada- ljevalni princip in strategija nami sljene igre, ki se izka ze za zelo uporabno tehniko dokazovanja. Nadaljevalni princip je formalizacija intuitivno jasne lastnosti, da se igra na grafu kon ca hitreje, ce so nekatera vozli s ca ze vna- prej dominirana, ki pa zahteva netrivialen dokaz. NajGjS ozna cuje graf G, na katerem so vozli s ca S V (G) ze dominirana, in naj g (GjS) ozna cuje stevilo potez v dominacijski igri na GjS, kjer prvo potezo naredi Dominator in vozli s c iz S ni ve c treba dominirati. Nadaljevalni princip pravi, da ce je G graf in B A V (G), potem velja g (GjA) g (GjB). Podobna lastnost velja tudi za igro, kjer za cne Zavla cevalka. Predstavljene so znane zgornje meje za igralno dominantno stevilo grafa. Leta 2013 so Kinnersley, West in Zamani postavili domnevo, da za vsak grafG brez izoliranih vozli s c in zn vozli s ci velja g (G) 3 5 n. Podobna domneva je se vedno odprta tudi za drevesa brez izoliranih vozli s c. Pri dokazovanju tovrstnih zgornjih mej je izredno uporabna metoda praznjenja Bujt aseve. Najbolj sa znana zgornja meja v splo snem je 5 8 n, ce se omejimo na grafe z najmanj so stopnjo 2, pa je dokazana zgornja meja 3 5 n. Posebej je studirana tudi podobna domneva, ki obravnava le grafe, ki premorejo Hamiltonovo pot (tj. pot v grafu, ki vsako vozli s ce obi s ce natanko enkrat). Za tak graf na n vozli s cih je domnevna zgornja meja enaka 1 2 n . Dolo canje igralnega dominantnega stevila ni enostavno niti na posame- znih dru zinah grafov. Avtorji predstavijo natan cne vrednosti za poti, cikle in njihove potence ter glavnike. Karakterizirani so gra, ki imajo igralno dominantno stevilo enako 2 ali 3. Posebna pozornost je namenjena vplivu 142 Obzornik mat. fiz.68 (2021) 4 i i \Irsic" | 2021/12/13 | 9:14 | page 143 | #3 i i i i i i Domination Games Played on Graphs odstranitve vozli s ca ali povezave na igralno dominantno stevilo grafa. Ker studirana invarianta za ti operaciji ni monotona, so tudi (povezavno) kri- ti cni gra denirani nekoliko druga ce kot obi cajno. Predstavljena je tudi casovna zahtevnost problema. V tretjem poglavju avtorji predstavijo znane rezultate o celotni domi- nacijski igri. Analogno z zgornjo mejo za igralno dominantno stevilo je postavljena domneva, da za vsak grafG nan vozli s cih, katerega vsaka kom- ponenta vsebuje vsaj tri vozli s ca, velja tg (G) 3 4 n. Natan cna vrednost celotnega igralnega dominantnega stevila je znana za poti, cikle in cikli cne dvodelne grafe. Predstavljeni so kriti cni in popolni gra, rezultati o vplivu odstranitve vozli s ca ter ra cunska zahtevnost problema. Ce si predstavljamo, da dominacijsko igro igra samo Dominator, je kon cna mno zica izbranih vozli s c ravno najmanj sa dominacijska mno zica grafa. Bolj zanimivo je torej studirati igro, ki jo igra samo Zavla cevalka in porodi t. i. Grundyjevo dominantno stevilo. Pri tej igri vozli s ca izbira le Zavla cevalka, njen cilj je se vedno kon cati igro s cim ve c izbranimi voz- li s ci, razli cna pravila za veljavnost poteze pa porodijo ve c razli cic igre. Tej igri (in njenim razli cicam) je posve ceno cetrto poglavje knjige. Posebej je izpostavljena povezava ene izmed razli cic z ni celno prisilo in najmanj sim rangom. Zadnje poglavje predstavi se preostale razli cice dominacijske igre. Med drugim spoznamo disjunktno dominacijsko igro, povezano dominacijsko igro, Z-, L- in LL-dominacijske igre ter nekatere igre na hipergrah. Pri disjunk- tni dominacijski igri eden izmed igralcev posku sa zgraditi dve disjunktni dominacijski mno zici, pri cemer mu drugi igralec posku sa to prepre citi. Po- vezana, Z-, L- in LL-dominacijska igra sledijo podobnim pravilom kot do- minacijska igra, le da so pogoji za veljavnost poteze nekoliko druga cni. Na koncu poglavja najdemo tudi strnjen pregled preostalih razli cic dominacij- ske igre { nekatere so se v literaturi pojavile ze pred letom 2010, vendar niso bile nikoli dele zne tolik sne pozornosti kot osnovna verzija dominacijske igre, ki jo obravnava opisana knjiga. Z jedrnatim pregledom denicij, rezultatov, metod dokazovanja in od- prtih problemov knjiga predstavlja odli cno referenco tako za bolj zagrete studente kot za trenutne in bodo ce raziskovalce na tem podro cju. Vesna Ir si c Obzornik mat. fiz.68 (2021) 4 143