← All problems

Improved upper bounds for Staller–Maker–Breaker domination numbers

17 years old · traced to

Let GG be a graph on nn vertices, with minimum degree δ(G)\delta(G). The S-game and D-game parameters are denoted by γSMB′(G)\gamma_{\rm SMB}'(G) and γSMB(G)\gamma_{\rm SMB}(G), respectively.

Improved SMBD-number bounds.

(i) If γSMB′(G)<∞, then γSMB′(G)≤⌈n2⌉−δ(G)+1;(ii) If γSMB(G)<∞, then γSMB(G)≤⌊n2⌋−δ(G)+1.\begin{aligned} &\text{(i) If }\gamma_{\rm SMB}'(G)<\infty,\text{ then }\gamma_{\rm SMB}'(G)\le \left\lceil\frac{n}{2}\right\rceil-\delta(G)+1;\\ &\text{(ii) If }\gamma_{\rm SMB}(G)<\infty,\text{ then }\gamma_{\rm SMB}(G)\le \left\lfloor\frac{n}{2}\right\rfloor-\delta(G)+1. \end{aligned}

These bounds would improve the known sharp general upper bounds when the minimum degree is at least two; the authors note that sharp examples under this degree condition are not known.

References

6 papers in this index state this conjecture (2009–2022). The statement above is taken from the most recent of them; the others are arXiv:2107.10805, arXiv:2106.01166, arXiv:1606.01317, arXiv:1503.07891, arXiv:0906.4142.

Source: Csilla Bujtás and Pakanun Dokyeesun, “Fast winning strategies for Staller in the Maker-Breaker domination game”, arXiv:2206.12812 (2022).

Progress summary

Refreshed
Open · progress reported

An unverified submission claims a small graph disproves both proposed improved bounds, but no independent confirmation was found.

A 2022 paper states these inequalities as Conjecture 7.2, improving the general upper bounds when the minimum degree is at least 22. It gives no proof and notes that sharp examples in this range were unknown.

Community submission (unverified), November 7, 2026

A submitted proof argues that a seven-vertex connected bipartite theta graph with branch lengths 2,2,42,2,4 has minimum degree 22 and Staller-start value 44, exceeding the proposed bound ⌈7/2⌉−2+1=3\left\lceil 7/2\right\rceil-2+1=3. It therefore claims a counterexample to part (i), and hence to the stated conjunction; no independently assessed evidence was retrieved.

Current status (as of November 2026): The conjectures remain unverified and are challenged by an unverified claimed counterexample to part (i); no verified resolution or independent assessment was found.

Sources

Solutions 1

A seven-vertex counterexample to the minimum-degree bound for Staller fast Maker-Breaker dominationSee full solutionHide full solution

Result and scope. Sevenvertex simple connected bipartite theta with branchlengths2,2,4 has minimumdegree2 and Staller-start optimalwinningnumber4>ceil(7/2)-2+1=3. Refutes Conjecture7.2(i) and thus MathDB355140 conjunction.

Complete proof: A seven-vertex counterexample to the minimum-degree bound for Staller fast Maker-Breaker domination · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.