Tout graphe dont la circonférence est supérieure à quatre a un cop number au moins égal à son degré minimal. Il s’ensuit qu’il existe des graphes de cop number arbitrairement élevé.
Quel est le plus grand cop number possible d’un n {\displaystyle n}.
-vertex graphe ?
Henri Meyniel (également connu pour les graphes de Meyniel) a conjecturé en 1985 que tout graphe n {\displaystyle n} connecté.
-vertex a un nombre de copies O ( n ) {\displaystyle O({\sqrt {n}})}.
. Les graphes de Levi (ou graphes d’incidence) des plans projectifs finis ont une circonférence de six et un degré minimal Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}.
, donc si elle est vraie cette borne serait la meilleure possible.
Tous les graphes ont un nombre de cops sublinéaire. Une façon de prouver cela est d’utiliser des sous-graphes qui sont gardables par un seul flic : le flic peut se déplacer pour suivre le voleur de telle manière que, si jamais le voleur se déplace dans le sous-graphe, le flic peut immédiatement capturer le voleur. Deux types de sous-graphe qui sont gardables sont le voisinage fermé d’un seul sommet, et le plus court chemin entre deux sommets. La borne de Moore dans le problème du diamètre des degrés implique qu’au moins un de ces deux types d’ensembles gardables a une taille Ω ( log n / log log n ) {\displaystyle \Omega (\log n/\log \log n)}.
. L’utilisation d’un cop pour garder cet ensemble et la récursion dans les composantes connectées des sommets restants du graphe montre que le nombre de cop est au plus O ( n log log n / log n ) {\displaystyle O(n\log \log n/\log n)}.
.
On connaît une limite supérieure plus fortement sous-linéaire sur le nombre de cop,
n 2 ( 1 – o ( 1 ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}
. Cependant les problèmes d’obtention d’une borne serrée, et de preuve ou de réfutation de la conjecture de Meyniel, restent non résolus. On ne sait même pas si la conjecture douce de Meyniel, selon laquelle il existe une constante c < 1 {\displaystyle c<1}.
pour laquelle le nombre de cop est toujours O ( n c ) {\displaystyle O(n^{c})}.
, est vrai.
Calculer le nombre de cop d’un graphe donné est EXPTIME-dur, et dur pour la complexité paramétrée.