부산대학교 도서관

The game of Cops and Robbers is a well‐known pursuit‐evasion game played on graphs. It has been proved that cubic graphs can have arbitrarily large cop number c(G), but the known constructions show only that the set {c(G)∣Gcubic} is unbounded. In this paper, we prove that there are arbitrarily large subcubic graphs G whose cop number is at least n1∕2−o(1) where n=∣V(G)∣. We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weaker version of Meyniel's conjecture for all graphs. [ABSTRACT FROM AUTHOR]