A join upper-bound conjecture for the hyperopic cop number

About 5 years old · traced to

Let GG and JJ be connected graphs. Write G∨JG\vee J for their graph join, cH(X)c_H(X) for the hyperopic cop number of a graph XX, and let Υ(X)\Upsilon(X) denote the maximum size of a common neighbourhood set in XX. Join upper-bound conjecture.

cH(G∨J)≤min⁡{cH(G),Υ(G)}+min⁡{cH(J),Υ(J)}.c_H(G\vee J) \leq \min\{c_H(G),\Upsilon(G)\}+\min\{c_H(J),\Upsilon(J)\}.

This is posed as an open question concerning small common neighbourhood sets. The difficulty is that the robber can access any vertex in the other graph, potentially interfering with winning strategies played by cops within GG and JJ; the paper also records weaker upper bounds involving c(G∨J)c(G\vee J) and the common-neighbourhood parameters.

References

Primary source

Nancy E. Clarke, Stephen Finbow, Margaret-Ellen Messinger and Amanda Porter, “A note on hyperopic cops and robber”, arXiv:2107.07368 (2021).

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.