Title: Waiter-Client Games on Randomly Perturbed Graphs
Abstract: Waiter-Client games are played on a hypergraph $$(X,\mathcal {F})$$ , where $$\mathcal {F} \subseteq 2^X$$ denotes the family of winning sets. During each round, Waiter offers a predefined amount (called bias) of elements from the board X, from which Client takes one for himself while the rest go to Waiter. Waiter wins the game if she can force Client to occupy any winning set $$F \in \mathcal {F}$$ . In this paper we consider Waiter-Client games played on randomly perturbed graphs. These graphs consist of the union of a deterministic graph $$G_\alpha $$ on n vertices with minimum degree at least $$\alpha n$$ and the binomial random graph $$G_{n,p}$$ . Depending on the bias 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}$$ .