Každý graf, jehož obvod je větší než čtyři, má kop číslo alespoň rovno svému minimálnímu stupni. Z toho vyplývá, že existují grafy s libovolně vysokým cop číslem.
Jaké je největší možné cop číslo n {\displaystyle n}.
-vrcholový graf?
Henri Meyniel (známý také díky Meynielovým grafům) v roce 1985 vyslovil domněnku, že každý spojitý n {\displaystyle n}
-vrcholový graf má kopové číslo O ( n ) {\displaystyle O({\sqrt {n}})}.
. Leviho grafy (nebo grafy incidence) konečných projektivních rovin mají obvod šest a minimální stupeň Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}
, takže pokud by tato hranice platila, byla by nejlepší možná.
Všechny grafy mají sublineární cop číslo. Jedním ze způsobů, jak to dokázat, je použít podgrafy, které jsou hlídatelné jedním policistou: policista se může pohybovat tak, aby sledoval lupiče, a to takovým způsobem, že pokud se lupič někdy do podgrafu přesune, může ho policista okamžitě chytit. Dva typy podgrafů, které jsou střežitelné, jsou uzavřené okolí jednoho vrcholu a nejkratší cesta mezi libovolnými dvěma vrcholy. Moorova hranice v problému průměru stupňů znamená, že alespoň jeden z těchto dvou typů hlídaných množin má velikost Ω ( log n / log log n ) {\displayystyle \Omega (\log n/\log \log n)}
. Použití jednoho copu ke střežení této množiny a rekurze v rámci spojených komponent zbývajících vrcholů grafu ukazuje, že počet copů je nejvýše O ( n log n / log n ) {\displaystyle O(n\log \log n/\log n)}
.
Je známa silněji sublineární horní mez pro cop číslo,
n 2 ( 1 – o ( 1 ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}
. Problémy získání těsné hranice a prokázání nebo vyvrácení Meynielovy domněnky však zůstávají nevyřešeny. Dokonce není známo, zda platí měkká Meynielova domněnka, že existuje konstanta c < 1 {\displaystyle c<1}.
pro kterou je cop číslo vždy O ( n c ) {\displaystyle O(n^{c})}
, je pravdivé.
Výpočet kopírovacího čísla daného grafu je EXPTIME-těžký a těžký pro parametrizovanou složitost
.