Care graf a cărui circumferință este mai mare decât patru are numărul cop cel puțin egal cu gradul său minim. Rezultă că există grafuri cu număr de cop arbitrar de mare.
Care este cel mai mare număr de cop posibil al unui n {\displaystyle n}
-un graf cuvertexuri?
Henri Meyniel (cunoscut și pentru grafurile Meyniel) a conchis în 1985 că orice graf conex n {\displaystyle n}
-vertex graph are numărul de cop O ( n ) {\displaystyle O({\sqrt {n}})}
. Grafurile Levi (sau grafurile de incidență) ale planurilor proiective finite au circumferința șase și gradul minim Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}
, astfel că, dacă este adevărată, această limită ar fi cea mai bună posibilă.
Toate grafurile au număr de cop sublinear. O modalitate de a demonstra acest lucru este de a folosi subgrafe care pot fi păzite de un singur polițist: polițistul se poate deplasa pentru a urmări hoțul în așa fel încât, dacă hoțul se deplasează vreodată în subgraf, polițistul îl poate captura imediat pe hoț. Două tipuri de subgrafe care pot fi păzite sunt vecinătatea închisă a unui singur vârf și calea cea mai scurtă între două vârfuri oarecare. Limita lui Moore în problema diametrului gradului implică faptul că cel puțin unul dintre aceste două tipuri de seturi păzibile are dimensiunea Ω ( log n / log log log n ) {\displaystyle \Omega (\log n/\log \log \log n)}.
. Folosind un polițist pentru a păzi acest set și recurgând în cadrul componentelor conectate ale celorlalte vârfuri ale grafului arată că numărul polițistului este de cel mult O ( n log log n / log n ) {\displaystyle O(n\log \log n/\log n)}.
.
Se cunoaște o limită superioară mai puternic sublineară pentru numărul cop,
n 2 ( 1 – o ( 1 ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}
este cunoscută. Cu toate acestea, problemele legate de obținerea unei limite strânse și de demonstrarea sau infirmarea conjecturii lui Meyniel rămân nerezolvate. Nu se știe nici măcar dacă conjectura moale a lui Meyniel, conform căreia există o constantă c < 1 {\displaystyle c<1}
pentru care numărul cop este întotdeauna O ( n c ) {\displaystyle O(n^{c})}
, este adevărată.
Calcularea numărului de cop al unui graf dat este EXPTIME-hard, și greu pentru complexitatea parametrizată.
.