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

From papers

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, n15n\geq 15, while for k=3k=3, n58n\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.