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

Let GG be a diameter-22 graph, let HGH\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.

Sources & referencesView supporting material

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.