En teoría de grafos , un gráfico de cubo plegado es un gráfico no dirigido formado a partir de un gráfico de hipercubo al agregarle una coincidencia perfecta que conecta pares opuestos de vértices de hipercubo.
El gráfico de cubo plegado de dimensión k (que contiene 2 k − 1 vértices) se puede formar agregando aristas entre pares opuestos de vértices en un gráfico de hipercubo de dimensión k − 1. (En un hipercubo con 2 n vértices, un par de vértices son opuesto si el camino más corto entre ellos tiene longitud n .) Puede, de manera equivalente, formarse a partir de un gráfico de hipercubo (también) de dimensión k , que tiene el doble de vértices, identificando juntos (o contrayendo) cada par de vértices opuestos.
Un gráfico de cubo plegado de dimensión k es un k - regular con 2 k − 1 vértices y 2 k − 2 k aristas.
El número cromático de la dimensión k gráfica del cubo plegado es dos cuando k es par (es decir, en este caso, la gráfica es bipartita ) y cuatro cuando k es impar. [1] La circunferencia impar de un cubo plegado de dimensión impar es k , por lo que para k impar mayor que tres, las gráficas de cubo plegado proporcionan una clase de gráficas sin triángulos con un número cromático cuatro y una circunferencia impar arbitrariamente grande. Como gráfico de distancia regular con circunferencia impar k y diámetro ( k − 1)/2, los cubos plegados de dimensión impar son ejemplos de gráficos impares generalizados . [2]
Cuando k es impar, la doble cubierta bipartita del cubo plegado de dimensión k es el cubo de dimensión k a partir del cual se formó. Sin embargo, cuando k es par, el cubo de dimensión k es una cubierta doble pero no la cubierta doble bipartita . En este caso, el cubo plegado ya es bipartito . Los gráficos de cubos plegados heredan de sus subgrafos de hipercubo la propiedad de tener un ciclo hamiltoniano , y de los hipercubos que los cubren doblemente la propiedad de ser un gráfico distancia-transitivo . [3]
Cuando k es impar, el cubo plegado de dimensión k contiene como subgrafo un árbol binario completo con 2 k − 1 nodos. Sin embargo, cuando k es par, esto no es posible, porque en este caso el cubo plegado es un gráfico bipartito con igual número de vértices en cada lado de la bipartición, muy diferente de la proporción de casi dos a uno para la bipartición de un árbol binario completo. [4]
En la computación paralela , se han estudiado los gráficos de cubos plegados como una potencial topología de red , como alternativa al hipercubo. Comparado con un hipercubo , un cubo plegado con el mismo número de nodos tiene casi el mismo grado de vértice pero sólo la mitad del diámetro . Se conocen algoritmos distribuidos eficientes (en relación con los de un hipercubo ) para transmitir información en un cubo plegado. [5]