The trap bound for restricted cop number in diameter-two graphs

At least 12 years old · documented by

Let GG be a diameter-22 graph, let H⊆GH\subseteq G be a subgraph, and let cG(H)c_G(H) denote the least number of ordinary cops needed to catch a robber restricted to HH, while the cops may move along all edges of GG. Call HH an ss-trap when the robber can be caught under the corresponding trap condition with parameter ss.

Restricted cop-number trap conjecture. If HH is an ss-trap in GG, then

cG(H)≤s.c_G(H)\leq s.

The paper says this conjecture could be used to improve the upper bounds, but gives no proof or counterexample.

References

Primary source

Zsolt Adam Wagner, “Cops and Robbers on diameter two graphs”, arXiv:1312.7555 (2014).

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.