En la teoría de grafos , una rama de las matemáticas, la k -ésima potencia G k de un grafo no dirigido G es otro grafo que tiene el mismo conjunto de vértices , pero en el que dos vértices son adyacentes cuando su distancia en G es como máximo k . Las potencias de grafos se denominan utilizando una terminología similar a la de la exponenciación de números: G 2 se llama el cuadrado de G , G 3 se llama el cubo de G , etc. [1]
Las potencias de un gráfico deben distinguirse de los productos de un gráfico consigo mismo, que (a diferencia de las potencias) generalmente tienen muchos más vértices que el gráfico original.
Si un grafo tiene diámetro d , entonces su potencia d -ésima es el grafo completo . [2] Si una familia de grafos tiene un ancho de camarilla acotado , entonces también lo tienen sus potencias d -ésimas para cualquier d fijo . [3]
La coloración de gráficos en el cuadrado de un gráfico se puede utilizar para asignar frecuencias a los participantes de las redes de comunicación inalámbrica de modo que ningún par de participantes interfiera entre sí en ninguno de sus vecinos comunes, [4] y para encontrar dibujos de gráficos con alta resolución angular . [5]
Tanto el número cromático como la degeneración de la k -ésima potencia de un grafo planar de grado máximo Δ son O (Δ ⌊ k /2⌋ ) , donde el límite de degeneración muestra que se puede utilizar un algoritmo de coloración voraz para colorear el grafo con esta cantidad de colores. [4] Para el caso especial de un cuadrado de un grafo planar, Wegner conjeturó en 1977 que el número cromático del cuadrado de un grafo planar es como máximo max(Δ + 5, 3Δ/2 + 1) , y se sabe que el número cromático es como máximo 5Δ/3 + O (1) . [6] [7] De manera más general, para cualquier grafo con degeneración d y grado máximo Δ , la degeneración del cuadrado del grafo es O ( d Δ) , por lo que muchos tipos de grafos dispersos distintos de los grafos planares también tienen cuadrados cuyo número cromático es proporcional a Δ .
Aunque el número cromático del cuadrado de un grafo no plano con grado máximo Δ puede ser proporcional a Δ 2 en el peor de los casos, es menor para grafos de gran circunferencia , estando acotado por O (Δ 2 / log Δ) en este caso. [8]
Determinar el número mínimo de colores necesarios para colorear el cuadrado de un gráfico es NP-difícil , incluso en el caso planar. [9]
El cubo de cada grafo conexo contiene necesariamente un ciclo hamiltoniano . [10] No es necesariamente el caso de que el cuadrado de un grafo conexo sea hamiltoniano, y es NP-completo determinar si el cuadrado es hamiltoniano. [11] Sin embargo, por el teorema de Fleischner , el cuadrado de un grafo conexo de 2 vértices es siempre hamiltoniano. [12]
La k -ésima potencia de un grafo con n vértices y m aristas se puede calcular en un tiempo O ( mn ) realizando una búsqueda en amplitud comenzando desde cada vértice para determinar las distancias a todos los demás vértices, o un poco más rápido utilizando algoritmos más sofisticados. [13] Alternativamente, si A es una matriz de adyacencia para el grafo, modificada para tener entradas distintas de cero en su diagonal principal, entonces las entradas distintas de cero de Ak dan la matriz de adyacencia de la k -ésima potencia del grafo, [14] de lo que se deduce que la construcción de k -ésimas potencias se puede realizar en una cantidad de tiempo que está dentro de un factor logarítmico del tiempo para la multiplicación de matrices .
Las potencias k -ésimas de los árboles se pueden reconocer en el tiempo lineal en el tamaño del gráfico de entrada. [15]
Dado un grafo, decidir si es el cuadrado de otro grafo es NP-completo . [16] Además, es NP-completo determinar si un grafo es una k- ésima potencia de otro grafo, para un número dado k ≥ 2 , o si es una k -ésima potencia de un grafo bipartito , para k > 2 . [17]
El semicuadrado de un grafo bipartito G es el subgrafo de G 2 inducido por un lado de la bipartición de G . Los grafos de mapa son los semicuadrados de los grafos planares , [18] y los grafos de cubos reducidos a la mitad son los semicuadrados de los grafos de hipercubos . [19]
Las potencias de hojas son los subgrafos de las potencias de los árboles inducidas por las hojas del árbol. Una potencia de k hojas es una potencia de hojas cuyo exponente es k . [20]
{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).