Número de copia

Todo grafo cuya circunferencia es mayor que cuatro tiene número de copia al menos igual a su grado mínimo. Se deduce que existen grafos de número de cop arbitrariamente alto.

Problema no resuelto en matemáticas:

¿Cuál es el mayor número de cop posible de un n {\displaystyle n}

-Gráfico de vértices?

Henri Meyniel (también conocido por los grafos de Meyniel) conjeturó en 1985 que todo n {displaystyle n} conectado

tiene un número de cop O ( n ) { {\displaystyle O({\sqrt {n}})}

. Los grafos de Levi (o grafos de incidencia) de los planos proyectivos finitos tienen circunferencia seis y grado mínimo Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}

, por lo que de ser cierto este límite sería el mejor posible.

Todos los grafos tienen un número de copia sublineal. Una forma de demostrar esto es utilizar subgrafos que son vigilables por un solo policía: el policía puede moverse para seguir al ladrón de tal manera que, si el ladrón se mueve alguna vez en el subgrafo, el policía puede capturar inmediatamente al ladrón. Dos tipos de subgrafos que son vigilables son la vecindad cerrada de un solo vértice y el camino más corto entre dos vértices cualesquiera. El límite de Moore en el problema del diámetro de grado implica que al menos uno de estos dos tipos de conjuntos guardables tiene un tamaño Ω ( log n / log n ) {\displaystyle \Omega (\log n/\log \log n)}

. Si se utiliza un policía para proteger este conjunto y se recorre dentro de las componentes conectadas de los vértices restantes del gráfico, se observa que el número de policías es como máximo O ( n log n / log n ) {\displaystyle O(n\log \log n/\log n)}.

.

Se conoce una cota superior más fuertemente sublineal del número de cop,

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

. Sin embargo, los problemas de obtener una cota ajustada, y de demostrar o refutar la conjetura de Meyniel, siguen sin resolverse. Incluso se desconoce si la conjetura blanda de Meyniel, de que existe una constante c < 1 {\displaystyle c<1}

para la cual el número de cop es siempre O ( n c ) {\displaystyle O(n^{c})}

, es verdadera.

Calcular el número de cop de un grafo dado es EXPTIME-difícil, y difícil para la complejidad parametrizada.