Jeder Graph, dessen Umfang größer als vier ist, hat eine Kopzahl, die mindestens so groß ist wie sein Mindestgrad. Daraus folgt, dass es Graphen mit beliebig hoher Kopzahl gibt.
Was ist die größtmögliche Kopzahl eines n {\displaystyle n}
-Vertex-Graphen?
Henri Meyniel (auch bekannt für Meyniel-Graphen) vermutete 1985, dass jeder zusammenhängende n {\displaystyle n}
-Verkreuzungsgraph die Kopzahl O ( n ) {\displaystyle O({\sqrt {n}})}
. Die Levi-Graphen (oder Inzidenzgraphen) endlicher projektiver Ebenen haben den Umfang sechs und den Mindestgrad Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}
, so dass diese Schranke, falls wahr, die bestmögliche wäre.
Alle Graphen haben eine sublineare Kopzahl. Eine Möglichkeit, dies zu beweisen, besteht darin, Untergraphen zu verwenden, die von einem einzelnen Polizisten bewacht werden können: Der Polizist kann sich so bewegen, dass er den Räuber verfolgt, und wenn sich der Räuber jemals in den Untergraphen hineinbewegt, kann der Polizist den Räuber sofort festnehmen. Zwei Arten von Teilgraphen, die überwachbar sind, sind die geschlossene Nachbarschaft eines einzelnen Scheitelpunkts und ein kürzester Weg zwischen zwei beliebigen Scheitelpunkten. Die Moore-Schranke im Grad-Durchmesser-Problem impliziert, dass mindestens eine dieser beiden Arten von bewachbaren Mengen die Größe Ω ( log n / log log n ) {\displaystyle \Omega (\log n/\log \log n)} hat.
. Die Verwendung eines Cops zur Bewachung dieser Menge und die Rekursion innerhalb der verbundenen Komponenten der verbleibenden Knoten des Graphen zeigt, dass die Anzahl der Cops höchstens O ( n log n / log n ) {\displaystyle O(n\log \log n/\log n)} ist
.
Eine stärker sublineare obere Schranke für die Kopzahl,
n 2 ( 1 – o ( 1 ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}
ist bekannt. Die Probleme, eine enge Schranke zu erhalten und die Meyniel-Vermutung zu beweisen oder zu widerlegen, bleiben jedoch ungelöst. Es ist sogar unbekannt, ob die weiche Meyniel-Vermutung, dass es eine Konstante c < 1 {\displaystyle c<1}
, für die die Kopzahl immer O ( n c ) {\displaystyle O(n^{c})}
, wahr ist.
Die Berechnung der Kopzahl eines gegebenen Graphen ist EXPTIME-schwer und schwer für parametrisierte Komplexität.