Jokainen graafi, jonka ympärysmitta on suurempi kuin neljä, on cop-luku vähintään yhtä suuri kuin sen minimiaste. Tästä seuraa, että on olemassa graafeja, joilla on mielivaltaisen suuri cop-luku.
Mikä on suurin mahdollinen cop-luku n {\displaystyle n}
-vertex-graafi?
Henri Meyniel (tunnetaan myös Meynielin graafeista) arveli vuonna 1985, että jokainen yhdistetty n {\displaystyle n}
-vertex-graafilla on kop-luku O ( n ) {\displaystyle O({\sqrt {n}})}
. Päättyneiden projektiivisten tasojen Levi-graafeilla (tai insidenssigraafeilla) on ympärysmitta kuusi ja minimiaste Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}
, joten jos pitää paikkansa, tämä raja olisi paras mahdollinen.
Kaikilla graafeilla on epälineaarinen kop-luku. Yksi tapa todistaa tämä on käyttää osa-graafeja, jotka ovat yhden poliisin vartioitavissa: poliisi voi liikkua ryöstäjää seuraamaan siten, että jos ryöstäjä joskus liikkuu osa-graafiin, poliisi voi heti ottaa ryöstäjän kiinni. Kaksi vartioitavaa aligrafiikkatyyppiä ovat yksittäisen kärkipisteen suljettu naapuruus ja lyhin polku minkä tahansa kahden kärkipisteen välillä. Mooren raja asteen läpimittaongelmassa merkitsee, että ainakin toisen näistä kahdesta vartioitavasta joukosta koko on Ω ( log n / log log log n ) {\displaystyle \Omega (\log n/\log \log \log n)}.
. Yhden kopin käyttäminen tämän joukon vartioimiseen ja rekursointi graafin jäljelle jäävien kärkipisteiden yhdistetyissä komponenteissa osoittaa, että kopin määrä on enintään O ( n log log n / log n ) {\displaystyle O(n\log \log n/\log n)}.
.
Tunnetaan vahvemmin sublineaarinen yläraja kopin luvulle,
n 2 ( 1 – o ( 1 ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}
. Tiukan rajan saamiseen ja Meynielin arvelun todistamiseen tai kumoamiseen liittyvät ongelmat ovat kuitenkin edelleen ratkaisematta. Ei edes tiedetä, onko pehmeä Meynielin olettamus, että on olemassa vakio c < 1 {\displaystyle c<1}
jolle kopin luku on aina O ( n c ) {\displaystyle O(n^{c})}
, on tosi.
Tietyn graafin kopliluvun laskeminen on EXPTIME-kovaa, ja vaikeaa parametrisoidulle kompleksisuudelle.