pith. sign in

arxiv: 2606.04824 · v1 · pith:VJM4I32Xnew · submitted 2026-06-03 · 🧮 math.CO

The minimum degree question for the Maker Breaker Domination Game

classification 🧮 math.CO
keywords betaboundgamegraphbreakerclaimdegreedomination
0
0 comments X
read the original abstract

The Maker Breaker Domination Game is a two player game played on a graph $G$ in which the players take turns to claim a vertex from the graph. The aim of the Dominator is to claim the vertices of a dominating set, and the aim of the Staller is to prevent this. In this paper, we consider the following problem: for a given integer $d$, what is the size of the smallest (with respect to the number of vertices) graph with minimum degree $d$ such that the Dominator loses going first? We write $\beta(d)$ to denote the answer to this question. We determine the precise value of $\beta(d)$ for $d\leq 3$. For general $d$ it was known that $2^{d+1} \leq \beta(d) \leq 2^{d+1}+2d$; the upper bound is due to a construction communicated to us by Valentin Gledel, while the lower bound follows from a simple application of the Erd\H{o}s-Selfridge Theorem. We improve the lower bound to $\beta(d) \geq 2^{d+1}+2$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.