2020/09/30 by Dennis Clemens, Fabian Hamann, Clemens, Dennis +5
Computer Science · Mathematics · #05C40 #05C45 #05C57 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2009.14583
openalex publication_date 2020/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Maker-Breaker games are played on a hypergraph (X,F), where F ⊆ 2X denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board X, and Maker wins the game if she is able to occupy any winning set F ∈ F. These games are well studied when played on the complete graph Kn or on a random graph Gn,p. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph Gα with minimum degree at least αn and a binomial random graph Gn,p. Depending on α and Breaker's bias b we determine the order of the threshold probability for winning the Hamiltonicity game and the k-connectivity game on Gα∪ Gn,p, and we discuss the H-game when b=1. Furthermore, we give optimal results for the Waiter-Client versions of all mentioned games.