Spanning Structures in Walker–Breaker Games

Article type: Research Article

Authors: Forcan, Jovana^{; *} | Mikalački, Mirjana^{; †}

Affiliations: Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Trg Dositeja Obradovića 4, 21000 Novi Sad, Serbia. dmi.jovana.jankovic@student.pmf.uns.ac.rs, mirjana.mikalacki@dmi.uns.ac.rs

Correspondence: [*] Also affiliated at: Department of Informatics, Faculty of Philosophy, University of East Sarajevo, Bosnia and Herzegovina. Address for correspondence: Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad.

Note: [†] The author’s research is partially supported by Ministry of Education, Science and Technological Development, Republic of Serbia, Grant No. 451-03-68/2022-14/200125.

Abstract: We study the biased (2 : b) Walker–Breaker games, played on the edge set of the complete graph on n vertices, Kn. These games are a variant of the Maker–Breaker games with the restriction that Walker (playing the role of Maker) has to choose her edges according to a walk. We look at the two standard graph games – the Connectivity game and the Hamilton Cycle game and show that Walker can win both games even when playing against Breaker whose bias is of the order of magnitude n/ ln n.

Keywords: positional games, Walker–Breaker games, spanning structures

DOI: 10.3233/FI-222104

Journal: Fundamenta Informaticae, vol. 185, no. 1, pp. 83-97, 2022