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

From papers

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 n1\sqrt{n-1}, so this conjecture would be close to best possible.

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

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

Solutions 0

No solutions have been posted yet.