Spanning Structures in Walker–Breaker Games.

• Autorzy: Forcan Jovana , Mikalački Mirjana

Identyfikatory

DOI

10.3233/FI-222104

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

positional games; spanning structures; Walker–Breaker games

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 1
• Strony: 83--97
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Forcan Jovana

autor

Mikalački Mirjana

Bibliografia

• [1] Espig L, Frieze A, Krivelevich M, Pegden W. Walker–Breaker games. SIAM Journal on Discrete Mathematics, 2015. 29(3):1476-1485. doi:10.1137/140953708.
• [2] Beck J. Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008. ISBN 9780511735202. doi:10.1017/CBO9780511735202. 1st Edition.
• [3] Hefetz D, Krivelevich M, Stojakovi´c M, Szab´o T. Positional Games. Springer Basel, Basel, 2014. ISBN 978-3-0348-0825-5.
• [4] Lehman A. A solution to Shannon switching game. Journal of the Society for Industrial and Applied Mathematics, 1964. 12(4):687- 725. doi:10.1137/0112059.
• [5] Hefetz D, Krivelevich M, Stojaković M, Szabó T. Fast winning strategies in Maker-Breaker games. Journal of Combinatorial Theory Series B, 2009. 99(1):39-47. doi:10.1016/j.jctb.2008.04.001.
• [6] Hefetz D, Stich S. On two problems regarding the Hamilton cycle game. Electronic Journal of Combinatorics, 2009. 16(1):Research Paper R28, 18 p.
• [7] Chvátal V, Erd˝os P. Biased positional games. Annals of Discrete Mathematics, 1978. 2(C):221-229. doi:10.1016/S0167-5060(08)70335-2.
• [8] Beck J. Remarks on positional games. I. Acta Mathematica Academiae Scientiarum Hungarica, 1982. 40:65-71.
• [9] Gebauer H, Szabó T. Asymptotic random graph intuition for the biased connectivity game. Random Structures and Algorithms, 2009. 35(4):431-443. doi:10.1002/rsa.20279.
• [10] Krivelevich M. The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n. Journal of the American Mathematical Society, 2011. 24(1):125-131. doi:10.1090/S0894-0347-2010-00678-9.
• [11] Hefetz D, Mikalački M, Stojakovi´c M. Doubly Biased Maker–Breaker Connectivity Game. The Electronic Journal of Combinatorics, 2012. 19(1):#P61. doi:10.37236/2129.
• [12] Mikalački M. Positional games on graphs. Ph.D. thesis, University of Novi Sad, 2013.
• [13] Balogh J, Martin R, Pluhár A. The diameter game. Random Structures and Algorithms, 2009. 35(3):369-389. doi:10.1002/rsa.20280.
• [14] Clemens D, Tran T. Creating cycles in Walker–Breaker games. Discrete Mathematics, 2016. 339(8):2113-2126. doi:10.1016/j.disc.2016.03.007.
• [15] West DB. Introduction to Graph Theory. Prentice Hall, 2001. ISBN 0-13-014400-2. 2nd Edition.
• [16] Lee C, Sudakov B. Dirac’s theorem for random graphs. Random Structures and Algorithms, 2012. 41(3):293-305. doi:10.1002/rsa.20419.
• [17] Ferber A, Krivelevich M, Naves H. Generating random graphs in biased Maker–Breaker games. Random Structures and Algorithms, 2015. 47(4):615-634. doi:10.1002/rsa.20619.
• [18] Alon N, Spencer J. The Probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 2008. ISBN 9780470170205. doi:10.1002/9780470277331. 3rd Edition.
• [19] Krivelevich M, Lee C, Sudakov B. Resilient pancyclicity of random and pseudorandom graphs. SIAM Journal on Discrete Mathematics, 2010. 24(1):1-16. doi:10.1137/090761148

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)