Improved upper bounds for Staller–Maker–Breaker domination numbers

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.

Sources & referencesView supporting material

Primary source

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

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

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.