Maker–Breaker games on graphs
Mejker–Brejker igre na grafovima
Докторанд
Forcan, JovanaМентор
Mikalački, MirjanaЧланови комисије
Mašulović, DraganMikalački, Mirjana
Stojaković, Miloš
Vukobratović, Dejan
Attribution-NonCommercial-ShareAlike
Метаподаци
Приказ свих података о дисертацијиСажетак
The topic of this thesis are different variants of Maker–Breaker positional game, where two players Maker and Breaker alternatively take turns in claiming unclaimed edges/vertices of a given graph. We consider Walker–Breaker game, played on the edge set of the graph Kn. Walker, playing the role of Maker is restricted to claim her edges according to a walk, while Breaker can claim any unclaimed edge per move. The focus is on two standard games - the Connectivity game, where Walker has the goal to build a spanning tree on Kn, and the Hamilton Cycle game, where Walker has the goal to build a Hamilton cycle on Kn. We show that Walker with bias 2 can win both games even when playing against Breaker whose bias b is of the order of magnitude n= ln n. Next, we consider (1 : 1) WalkerMaker–WalkerBreaker game on E(Kn),where both Maker and Breaker are walkers and we are interested in seeing how fast WalkerMaker can build spanning tree and Hamilton cycle. Finally, we study Maker–Breaker total domi...nation game played on the vertex set of a given graph. Two players, Dominator and Staller, alternately take turns in claiming unclaimed vertices of the graph. Staller is Maker and wins if she can claim an open neighbourhood of a vertex. Dominator is Breaker and wins if he manages to claim a total dominating set of a graph. For certain connected cubic graphs on n ≥ 6 vertices, we give the characterization of those graphs which are Dominator’s win and those which are Staller’s win.
Tema istrazivanja ove disertacije su igre tipa Mejker– Brejker u kojima uˇcestvuju dva igraˇca, Mejker i Brejker, koji naizmjeniˇcno uzimaju slobodne grane/ˇcvorove datog grafa. Bavimo se Voker–Brejker igrama koje se igraju na skupu grana grafa Kn. Voker, u ulozi Mejkera, jeograniˇcen da uzima svoje grane kao da se ˇseta kroz graf, dok Brejker moˇze da uzme bilo koju slobodnu granu grafa. Fokus je na dvije standardne igre - igri povezanosti, gdje Voker ima za cilj da napravi pokrivaju´ce stablo grafa Kn i igri Hamiltonove konture, gdje Voker ima za cilj da napravi Hamiltonovu konturu. Brejker pobjeduje ako sprijeˇci Vokera u ostvarenju njegovog cilja. Pokaza´cemo da Voker sa biasom 2 moˇze da pobijedi u obje igre ˇcak i ako igra protiv Brejkera ˇciji je bias b reda n= ln n. Potom razmatramo (1 : 1) VokerMejker–VokerBrejker igre na Kn, gdje oba igraˇca, i Mejker i Brejker, moraju da biraju grane koje su dio ˇsetnje u njihovom grafu s ciljem odredivanja brze pobjedniˇce strategije VokerM...ejkera u igri povezanosti i igri Hamiltonove konture. Konaˇcno, istraˇzujemo Mejker–Brejker igre totalne dominacije koje se igraju na skupu ˇcvorova datog grafa. Dva igraˇca, Dom inator i Stoler naizmjeniˇcno uzimaju slobodne ˇcvorove datog grafa. Stoler je Mejker i pobjeduje ako uspije da uzme sve susjede nekog ˇcvora. Dominator je Brejker i pobjeduje ako ˇcvorovi koje uzme dok kraja igre formiraju skup totalne dominacije. Za odredene klase povezanih kubnih grafova reda n ≥ 6, dajemo karakterizaciju onih grafova na kojima Dominator pobjeduje i onih na kojima Stoler pobjeduje.
Факултет:
Универзитет у Новом Саду, Природно-математички факултетДатум одбране:
25-01-2022Кључне речи:
Positional games on graphs / Positional games on graphs / Maker–Breaker games / spanning tree / Hamilton cycle / total domination games / cubic graphs / Maker–Breaker games / spanning tree / Hamilton cycle / total domination games / cubic graphsОстали линкови:
Related items
Showing items related by title, author, creator and subject.
-
Neke klase grafova sa datim ograničenjima druge sopstvene vrednosti / Some classes of graphs with given bound for second largest eigenvalue
Mihailović, Bojana Lj. (Универзитет у Београду, Математички факултет, 14-07-2016) -
Анализа прстена и модула придруживањем графова / The Analysis of the rings and modules using associated graphs
Pucanović, Zoran S. (Универзитет у Београду, Математички факултет, 22-03-2013) -
Neke klase spektralno ograničenih grafova / Some classes of spectrally constrained graphs
Koledin, Tamara D. (Универзитет у Београду, Математички факултет, 08-07-2013)