胴回りが4より大きいグラフはすべて、少なくともその最小次数に等しいコップ数を持つ。 このことから、任意に高いcop numberのグラフが存在することがわかる。
What is the largest possible cop number of an n {displaystyle n}.
-頂点のグラフ？
Henri Meyniel (Meyniel graphsでも有名)は1985年に、すべての連結されたn{displaystyle n}グラフは、以下のようになることを予想しました。
-頂点グラフはコップ数O（ n ）{ {displaystyle O({}sqrt {n}})} を持つ。
。 有限射影平面のLeviグラフ（または入射グラフ）は胴回り6、最小次数ω ( n ) { {displaystyle \Omega ({\sqrt {n}})} である。
, もし本当ならこの境界は最良のものであろう。
全てのグラフはサブリニアコップ数を持つ。 このことを証明する一つの方法は、警官一人が警備可能な部分グラフを使うことである。警官は強盗を追跡するために移動することができるので、強盗がその部分グラフに移動した場合、警官はすぐに強盗を捕らえることができるのである。 ガード可能な部分グラフには、1つの頂点の閉じた近傍と、任意の2つの頂点間の最短路の2種類がある。 degree diameter問題のMoore boundは、これら2種類のGuardableセットのうち少なくとも1つのサイズがΩ ( log n / log log n ) {displaystyle \Omega (\log n/log \log n)}であることを意味している。
. このセットを守るために1つのcopを使い、グラフの残りの頂点の連結成分内を再帰すると、cop数は最大でO ( n log log n / log n ) {displaystyle O(nlog \log n/log n)}であることがわかる。
.
cop number,
n 2 ( 1 – o ( 1 ) ) log n , { {displaystyle { {frac {n}{2^{(1-o(1)){sqrt {log n}}}}, }
より強くサブリニアの上界も知られています。 しかし、厳密な境界を得る問題や、Meynielの予想の証明や反証は未解決のままである。 定数c < 1 {displaystyle c<1} が存在するという柔らかいMeyniel予想が成り立つかどうかも不明である。
for that the cop number is always O ( n c ) {displaystyle O(n^{c})}}.
, は真である。
与えられたグラフのコップ数を計算するのはEXPTIME-hardであり、パラメータ化された複雑さではhardである
。