Varje graf vars omkrets är större än fyra har ett cop-nummer som är minst lika stort som dess lägsta grad. Av detta följer att det finns grafer med godtyckligt högt cop-nummer.
Vad är det största möjliga cop-nummeret för en n {\displaystyle n}
-vertexgraf?
Henri Meyniel (även känd för Meynielgrafer) antog 1985 att varje sammanhängande n {\displaystyle n}
-vertexgraf har cop number O ( n ) {\displaystyle O({\sqrt {n}})}
. Levi-graferna (eller incidensgraferna) för ändliga projektiva plan har omkrets sex och lägsta grad Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}
, så om det är sant skulle denna gräns vara den bästa möjliga.
Alla grafer har sublinjärt cop-nummer. Ett sätt att bevisa detta är att använda undergrafer som kan bevakas av en enda polis: polisen kan röra sig för att följa rånaren på ett sådant sätt att om rånaren någonsin rör sig in i undergrafen kan polisen omedelbart fånga rånaren. Två typer av undergrafer som kan bevakas är det slutna grannskapet till en enda topp och den kortaste vägen mellan två toppar. Moores gräns i problemet med graddiameter innebär att minst en av dessa två typer av bevakningsbara uppsättningar har en storlek Ω ( log n / log log log n ) {\displaystyle \Omega (\log n/\log \log n)}
. Om man använder en polis för att bevaka denna mängd och sedan går tillbaka till de anslutna delarna av de återstående hörnen i grafen visar det sig att antalet poliser är högst O ( n log log log n / log n ) {\displaystyle O(n\log \log n/\log n)}
.
En starkare sublinjär övre gräns för cop-talet,
n 2 ( 1 – o ( 1 ) ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}
är känd. Problemen med att erhålla en snäv gräns och med att bevisa eller motbevisa Meyniels gissning är dock fortfarande olösta. Det är till och med okänt om Meyniels mjuka gissning, att det finns en konstant c < 1 {\displaystyle c<1}
för vilken cop-talet alltid är O ( n c ) {\displaystyle O(n^{c})}
, är sant.
Beräkna cop-numret för en given graf är EXPTIME-hårt, och svårt för parametrerad komplexitet.