Degree Game for Special Regular Graphs

Abstract

For a given $d$-regular graph $G$, a Maker-Breaker degree game is played by two players who alternately claim previously unclaimed edges of $G$. In the standard variant, the goal of Maker is to maximize the maximum degree of their induced subgraph, while Breaker aims to minimize it, or equivalently, to guarantee a certain minimum degree in their own subgraph. A classic pairing strategy shows that Breaker can secure at least $\lfloor d/4 \rfloor$ edges at every vertex of any $d$-regular graph. Breaking this bound for general or even for specific classes of graphs has been a long-standing open problem in combinatorial game theory; indeed, J. Beck characterized this challenge in his monograph as the first among the seven most humiliating open problems of positional game theory. In this paper, we improve the $d/4$ bound for some infinite graph families, such as the hypercube graph $Q_d$, grids and tori. We first show that Breaker can secure a degree of one at every vertex in $Q_3$, then lift this to higher dimensions, where Breaker can guarantee a degree of at least $\lfloor d/3 \rfloor$.

Disclosure

“st gratitude to András Pluhár. His insightful comments, valuable suggestions, and constant encouragement were indis- pensable throughout the brainstorming sessions and the writing of this paper. Declaration on the use of generative AI. Gemini was used in a limited manner during manuscript preparation for language editing and organizational assistance. References [1] J. Balogh, A. Pluhár, The positive minimum degree game on sparse graph”

PDF page 12

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T05:10:08.708758Z

Structural counts