Cop-nummer

Uopklaret problem i matematik:

Hvad er det størst mulige cop-nummer for en n {\displaystyle n}

-vertexgrafen?

Henri Meyniel (også kendt for Meyniel-grafer) formodede i 1985, at enhver sammenhængende n {\displaystyle n}

-vertex-graf har cop-nummer O ( n ) {\displaystyle O({\sqrt {n}})}

. Levi-graferne (eller incidensgraferne) af finitte projektive planer har omkreds seks og mindste grad Ω ( n ) {\displaystyle \Omega ({\sqrt {n}}})}

, så hvis det var sandt, ville denne grænse være den bedst mulige.

Alle grafer har sublineært cop-tal. En måde at bevise dette på er at bruge undergrafer, der kan bevogtes af en enkelt betjent: betjenten kan bevæge sig for at følge røveren på en sådan måde, at hvis røveren nogensinde bevæger sig ind i undergrafen, kan betjenten straks fange røveren. To typer af undergrafer, der kan bevogtes, er det lukkede kvarter til et enkelt toppunkt og den korteste vej mellem to toppunkter. Moore-begrænsningen i diameterproblemet indebærer, at mindst en af disse to typer af bevogtningsbare mængder har en størrelse Ω ( log n / log log log n ) {\displaystyle \Omega (\log n/\log \log n)}

. Ved at bruge en cop til at bevogte dette sæt og genbruge inden for de forbundne komponenter af de resterende hjørner i grafen viser det sig, at cop-nummeret højst er O ( n log log log n / log n ) {\displaystyle O(n\log \log n/\log n)}

.

En mere stærkt sublineær øvre grænse for cop-tallet,

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

er kendt. Problemerne med at opnå en snæver grænse og med at bevise eller modbevise Meyniels formodning er imidlertid fortsat uløste. Det er endog ukendt, om den bløde Meynielforestilling, at der findes en konstant c < 1 {\displaystyle c<1}

for hvilken cop-tallet altid er O ( n c ) {\displaystyle O(n^{c})}

, er sandt.

Beregning af cop-nummeret for en given graf er EXPTIME-hårdt, og hårdt for parameteriseret kompleksitet.