Maker–Breaker games on graphs

Abstract

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 domination 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 VokerMejkera 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.