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

Jakob F\"uhrer , Georg Grasegger , Paul Hametner , Oliver Roche-Newton This is my paper

Pith reviewed 2026-06-28 05:35 UTC · model grok-4.3

classification 🧮 math.CO
keywords Maker-Breaker gamedomination gameminimum degreebeta(d)positional gameErdős-Selfridgedominating setgraph theory
0
0 comments X

The pith

The exact value of β(d) is determined for d ≤ 3 and the general lower bound is raised to 2^{d+1} + 2 in the Maker-Breaker Domination Game.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the Maker-Breaker Domination Game played on graphs where players alternately claim vertices. Dominator wins by claiming all vertices of some dominating set while Staller tries to block this. β(d) measures the smallest number of vertices possible in a graph with minimum degree at least d for which Dominator loses when moving first. The authors compute this number exactly when the minimum degree is at most 3. They also prove a stricter lower bound of 2 to the power of d plus 1 plus 2 for any d by using a more detailed counting argument than the standard Erdős-Selfridge theorem.

Core claim

For d ≤ 3 we determine the precise value of β(d). For general d we improve the known lower bound from 2^{d+1} to 2^{d+1} + 2 while the upper bound remains 2^{d+1} + 2d.

What carries the argument

The function β(d) tracking the minimal order of a minimum-degree-d graph in which the second player wins the Maker-Breaker Domination Game.

If this is right

  • The values of β(d) are now known exactly for every d from 0 to 3.
  • The lower bound on β(d) is increased by 2 for every d.
  • Any graph with minimum degree d and fewer than 2^{d+1} + 2 vertices must allow Dominator a winning strategy when starting.
  • The construction achieving the upper bound of 2^{d+1} + 2d may not be minimal for small d.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The counting technique could extend to variants of the game with different winning conditions.
  • Finding whether β(d) equals 2^{d+1} + 2 for d > 3 would require new constructions or stronger bounds.
  • These minimal graphs might reveal structural properties useful for analyzing domination in game settings on sparse graphs.

Load-bearing premise

The refined counting argument used to improve the bound fully accounts for all legal plays and all possible dominating sets without missing any cases.

What would settle it

Discovery of a minimum-degree-d graph with 2^{d+1} + 1 vertices where the first player still loses the game would disprove the improved lower bound.

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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the Maker-Breaker Domination Game on graphs of minimum degree d. It defines β(d) as the smallest order of such a graph on which the first player (Dominator) loses. The authors determine the exact value of β(d) for all d ≤ 3 and prove the improved general lower bound β(d) ≥ 2^{d+1} + 2 (strengthening the Erdős-Selfridge application that gave only 2^{d+1}), while the known upper bound remains 2^{d+1} + 2d.

Significance. If the proofs hold, the exact determination for d ≤ 3 supplies concrete, verifiable benchmarks that can be used to test future general conjectures, while the tightened lower bound narrows the gap to the upper bound and demonstrates that a refined counting argument can extract an extra additive constant beyond the standard positional-game criterion. The manuscript thereby advances the quantitative understanding of degree-constrained Maker-Breaker games.

minor comments (3)
  1. §2 (preliminaries): the definition of a legal move under the domination condition is stated only informally; an explicit sentence clarifying whether a vertex claimed by Staller can block domination even if it is not itself dominated would remove ambiguity for readers unfamiliar with the game variant.
  2. Theorem 3.1 (exact value for d=3): the case analysis is presented via a sequence of claims; adding a short table that lists the critical subcases and the number of moves remaining would improve readability without lengthening the proof.
  3. The citation to the Erdős-Selfridge theorem in the introduction should include the precise reference (year and venue) rather than the name alone, consistent with the citation style used for Gledel’s construction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external theorems and independent case analysis

full rationale

The paper's lower bound β(d) ≥ 2^{d+1} follows directly from the external Erdős-Selfridge theorem (cited as a simple application, not derived internally). The upper bound is attributed to an external construction by Valentin Gledel. The exact determination of β(d) for d ≤ 3 is obtained via exhaustive case analysis on small graphs, which does not reduce to any fitted parameter, self-definition, or self-citation chain. No load-bearing step equates a claimed result to its own inputs by construction, and all cited results are independent external sources. This is a standard non-circular combinatorial argument structure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the standard definition of dominating sets and the applicability of the Erdős-Selfridge theorem to this game; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption The Erdős-Selfridge theorem applies directly to the Maker-Breaker domination game to yield the base lower bound of 2^{d+1}.
    Abstract states that the previous lower bound follows from a simple application of this theorem.

pith-pipeline@v0.9.1-grok · 5742 in / 1236 out tokens · 34927 ms · 2026-06-28T05:35:33.725374+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

12 extracted references · 3 canonical work pages

  1. [1]

    Partition strategies for the Maker-Breaker domination game

    Guillaume Bagan and Eric Duchêne and Valentin Gledel and Tuomo Lehtilä and Aline Parreau. Partition strategies for the Maker-Breaker domination game. Algorithmica. 2025. doi:10.1007/s00453-024-01280-x

    work page doi:10.1007/s00453-024-01280-x 2025

  2. [2]

    Domination game and an imagination strategy , JOURNAL =

    Bre. Domination game and an imagination strategy , JOURNAL =. 2010 , NUMBER =

    2010

  3. [3]

    Maker-breaker domination game

    Eric Duchêne and Valentin Gledel and Aline Parreau and Gabriel Renault. Maker-breaker domination game. Discrete Math. 2020. doi:10.1016/j.disc.2020.111955

    work page doi:10.1016/j.disc.2020.111955 2020

  4. [4]

    , title =

    Erdős, Paul and Selfridge, John L. , title =. Journal of Combinatorial Theory, Series A , volume =. 1973 , doi =

    1973

  5. [5]

    Discrete Mathematics & Theoretical Computer Science

    Forcan, Jovana and Qi, Jiayue , title =. Discrete Mathematics & Theoretical Computer Science. DMTCS. , volume =. 2024 , doi =

    2024

  6. [6]

    Positional games , series =

    Hefetz, Dan and Krivelevich, Michael and Stojakovi\'. Positional games , series =. 2014 , doi =

    2014

  7. [7]

    McKay and Adolfo Piperno , title =

    Brendan D. McKay and Adolfo Piperno , title =. Journal of Symbolic Computation , volume =. 2014 , doi =

    2014

  8. [8]

    , title =

    Tutte, William T. , title =. Proceedings of the American Mathematical Society , volume =. 1953 , doi =

    1953

  9. [9]

    Tutte , title =

    William T. Tutte , title =. Journal of The London Mathematical Society-second Series , year =

  10. [10]

    Factors and factorizations of graphs: Proof techniques in factor theory

    Jin Akiyama and Mikio Kano. Factors and factorizations of graphs: Proof techniques in factor theory. 2011. doi:10.1007/978-3-642-21919-1

    work page doi:10.1007/978-3-642-21919-1 2011

  11. [11]

    2008 , doi =

    Beck, József , title =. 2008 , doi =

    2008

  12. [12]

    Jakob Führer and Georg Grasegger and Paul Hametner and Oliver Roche-Newton , title =