The square-root bound for the cop number of diameter-two graphs

At least 12 years old · documented by

Let GG be a graph of diameter 22 and order nn, and let c(G)c(G) denote its cop number.

Square-root bound conjecture. One should have

c(G)≤n.c(G)\leq \sqrt{n}.

The paper proves the weaker bound c(G)≤2nc(G)\leq \sqrt{2n} and notes that Moore graphs have cop number n−1\sqrt{n-1}, so this conjecture would be close to best possible.

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.