Każdy graf, którego obwód jest większy od czterech, ma cop number co najmniej równy jego minimalnemu stopniowi. Wynika stąd, że istnieją grafy o arbitralnie dużej liczbie cop.
Jaka jest największa możliwa liczba cop dla grafu n {{przykład n}
grafu wierzchołkowego?
Henri Meyniel (znany również z grafów Meyniela) wysunął w 1985 roku przypuszczenie, że każdy połączony n {{displaystyle n}
-wertex graph has cop number O ( n ) {displaystyle O({sqrt {n}})}
. Grafy Leviego (lub incidence graphs) skończonych płaszczyzn rzutowych mają obwód sześć i minimalny stopień Ω ( n ) {displaystyle O({sqrt {n})}.
, więc jeśli jest to prawda, ta granica byłaby najlepsza z możliwych.
Wszystkie grafy mają podliniową liczbę kopiową. Jednym ze sposobów na udowodnienie tego jest użycie podgrafów, które są strzeżone przez jednego policjanta: policjant może poruszać się tak, aby śledzić rabusia w taki sposób, że jeśli rabuś kiedykolwiek poruszy się w podgrafie, policjant może natychmiast schwytać rabusia. Dwa rodzaje podgrafów, które są strzeżone, to zamknięte sąsiedztwo pojedynczego wierzchołka oraz najkrótsza ścieżka między dwoma dowolnymi wierzchołkami. Granica Moore’a w problemie średnicy stopnia implikuje, że przynajmniej jeden z tych dwóch rodzajów zbiorów możliwych do strzeżenia ma rozmiar Ω ( log n / log log log n ) {{displaystyle \Omega (\log n/ \log \log n)}
. Użycie jednego policjanta do pilnowania tego zbioru i rekurencja w połączonych składowych pozostałych wierzchołków grafu pokazuje, że liczba policjantów wynosi co najwyżej O ( n log log n / log n ) {displaystyle O(n log n/log n)}.
.
Silniej subliniowe górne ograniczenie na liczbę cop,
n 2 ( 1 – o ( 1 ) ) log n , {displaystyle {frac {n}{2^{(1-o(1))} log n}}}}},}
jest znane. Nierozwiązane pozostają jednak problemy uzyskania ścisłej granicy oraz udowodnienia lub obalenia domysłu Meyniela. Nie wiadomo nawet, czy istnieje miękkie przypuszczenie Meyniela, że istnieje stała c < 1 {{displaystyle c<1}}.
dla której liczba cop jest zawsze O ( n c ) {displaystyle O(n^{c})}
, jest prawdziwe.
Obliczanie liczby cop danego grafu jest EXPTIME-hard, i trudne dla parametryzowanej złożoności.
.