Minimal-order conjecture for graphs with large attacking-cop-number gap

About 2 years old · traced to

Let HH be a graph of order nn, and let c⁡(H)\operatorname{c}(H) and cc⁡(H)\operatorname{cc}(H) denote its cop number and attacking cop number, respectively.

Minimal-order conjecture for the attacking-cop-number gap. If

cc⁡(H)−c⁡(H)≥k,\operatorname{cc}(H)-\operatorname{c}(H)\geq k,

then, for k=2k=2, n≥15n\geq 15, while for k=3k=3, n≥58n\geq 58.

This conjecture asserts that the known constructions with attacking cop number exceeding the cop number by two or three have minimal possible order. The source presents it as a conjecture about the minimality of the known examples.

References

Primary source

Alexander Clow, Melissa A. Huggan and M. E. Messinger, “Cops and Attacking Robbers with Cycle Constraints”, arXiv:2408.02225 (2024).

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.