TUHH / Institut für Mathematik / Forschungsgebiete / Maker-Breaker games on randomly perturbed graphs

# Maker-Breaker games on randomly perturbed graphs

## Description

Maker-Breaker games are played on a hypergraph $$(X,\mathcal{F})$$, where $$\mathcal{F} \subseteq 2^X$$ denotes the family of winning sets. Both players alternately claim a predefined number (called bias) of unclaimed edges from the board $$X$$, and Maker wins the game if she is able to occupy any winning set $$F \in \mathcal{F}$$. These games are well studied when played on the complete graph $$K_n$$ or on a random graph $$G_{n,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_\alpha$$ with minimum degree at least $$\alpha n$$ and a binomial random graph $$G_{n,p}$$. Depending on $$\alpha$$ 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_{\alpha}\cup G_{n,p}$$, and we discuss the $$H$$-game when $$b=1$$.