En 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 . Se hace referencia a las potencias de las gráficas utilizando una terminología similar a la de la exponenciación de números: G 2 se llama cuadrado de G , G 3 se llama cubo de G , etc.
Las potencias de los gráficos 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 una gráfica tiene un diámetro d , entonces su d -ésima potencia es la gráfica completa . [2] Si una familia de gráficos tiene un ancho de camarilla acotado , también lo tienen sus d -ésimas potencias 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 redes de comunicación inalámbrica de modo que dos participantes no interfieran 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 gráfico plano 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 codiciosa para colorear el gráfico con este muchos colores. [4] Para el caso especial de un cuadrado de un gráfico plano, Wegner conjeturó en 1977 que el número cromático del cuadrado de un gráfico plano es como máximo max(Δ + 5,3Δ/2+ 1) , y se sabe que el número cromático es como máximo5Δ/3+ O (1) . [6] [7] De manera más general, para cualquier gráfico con degeneración d y grado máximo Δ , la degeneración del cuadrado del gráfico es O ( d Δ) , por lo que muchos tipos de gráficos dispersos distintos de los gráficos planos también tienen cuadrados cuyos El número cromático es proporcional a Δ .
Aunque el número cromático del cuadrado de un gráfico no plano con grado máximo Δ puede ser proporcional a Δ 2 en el peor de los casos, es menor para gráficos 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 plano. [9]
El cubo de todo gráfico conexo contiene necesariamente un ciclo hamiltoniano . [10] No es necesariamente el caso de que el cuadrado de un gráfico conectado sea hamiltoniano, y es NP-completo determinar si el cuadrado es hamiltoniano. [11] Sin embargo, según el teorema de Fleischner , el cuadrado de un gráfico conectado con 2 vértices es siempre hamiltoniano. [12]
La k -ésima potencia de un gráfico con n vértices ym aristas se puede calcular en el tiempo O ( mn ) realizando una primera 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 usando algoritmos más sofisticados. [13] Alternativamente, si A es una matriz de adyacencia para el gráfico, modificada para tener entradas distintas de cero en su diagonal principal, entonces las entradas distintas de cero de A k dan la matriz de adyacencia de la k -ésima potencia del gráfico, [14] de la cual de ello 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 k -ésimas potencias de los árboles se pueden reconocer en el tiempo lineal en el tamaño del gráfico de entrada. [15]
Dado un gráfico, decidir si es el cuadrado de otro gráfico es NP-completo . [16] Además, es NP-completo determinar si un gráfico es una k -ésima potencia de otro gráfico, para un número dado k ≥ 2 , o si es una k -ésima potencia de un gráfico bipartito , para k > 2 . [17]
El semicuadrado de un gráfico bipartito G es el subgrafo de G 2 inducido por un lado de la bipartición de G . Los gráficos de mapas son los semicuadrados de los gráficos planos , [18] y los gráficos de cubos partidos por la mitad son los semicuadrados de los gráficos de hipercubo . [19]
Los poderes de las hojas son los subgrafos de los poderes de los árboles inducidos por las hojas del árbol. Una k potencia de hoja es una potencia de hoja cuyo exponente es k . [20]
{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace ).