Cop szám

Minden olyan gráfnak, amelynek a kerülete nagyobb, mint négy, a cop száma legalább a minimális fokszámával egyenlő. Ebből következik, hogy léteznek tetszőlegesen nagy cop-számú gráfok.

Megoldatlan matematikai probléma:

Melyik a legnagyobb lehetséges cop-szám egy n {\displaystyle n}

-vertex gráfjának?

Henri Meyniel (a Meyniel-gráfokról is ismert) 1985-ben feltételezte, hogy minden összefüggő n {\displaystyle n}

-vertex gráfnak O ( n ) {\displaystyle O({\sqrt {n}})} kópiaszáma van.

. A véges vetületi síkok Levi-gráfjainak (vagy incidencia-gráfjainak) kerülete hat és minimális foka Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}

, tehát ha igaz, akkor ez a korlát lenne a lehető legjobb.

Minden gráfnak szublineáris kopszámmal rendelkezik. Ennek bizonyításának egyik módja, hogy olyan részgráfokat használunk, amelyek egyetlen zsaru által őrizhetők: a zsaru úgy mozoghat a rabló követésére, hogy ha a rabló valaha is bemegy a részgráfba, a zsaru azonnal elfoghatja a rablót. Az őrzésre alkalmas részgráfok két típusa egyetlen csúcs zárt szomszédsága, illetve a két csúcs közötti legrövidebb út. A Moore-féle korlát a fokátmérő problémában azt jelenti, hogy a kétféle őrzhető halmaz közül legalább az egyiknek Ω ( log n / log log log n ) méretű {\displaystyle \Omega (\log n / \log \log \log n)}

. Ha egy zsarut használunk ennek a halmaznak az őrzésére, és a gráf fennmaradó csúcsainak összefüggő komponenseiben keresünk, akkor a zsaruk száma legfeljebb O ( n log log n / log n ) {\displaystyle O(n\log \log n/\log n)}.

.

Egy erősebben szublineáris felső korlát a kop számra,

n 2 ( 1 – o ( 1 ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}

ismert. Megoldatlanok maradtak azonban a szűk korlát megszerzésének, valamint Meyniel sejtésének bizonyításának vagy cáfolatának problémái. Még az is ismeretlen, hogy a lágy Meyniel-féle sejtés, miszerint létezik egy c < 1 {\displaystyle c<1} konstans {\displaystyle c<1}

amelyre a kopszám mindig O ( n c ) {\displaystyle O(n^{c})}

, igaz.

Egy adott gráf kópiaszámának kiszámítása EXPTIME-nehez, és nehéz a paraméterezett bonyolultság szempontjából.