En teoría de grafos , un grafo cúbico plegado es un grafo no dirigido formado a partir de un grafo hipercubico añadiéndole una correspondencia perfecta que conecta pares opuestos de vértices hipercubicos.
El grafo cúbico plegado de dimensión k (que contiene 2 k − 1 vértices) se puede formar añadiendo aristas entre pares opuestos de vértices en un grafo hipercubo de dimensión k − 1. (En un hipercubo con 2 n vértices, un par de vértices son opuestos si el camino más corto entre ellos tiene una longitud n ). Se puede formar, de manera equivalente, a partir de un grafo hipercubo (también) de dimensión k , que tiene el doble de vértices, identificando juntos (o contrayendo) cada par opuesto de vértices.
Un grafo cúbico plegado de dimensión k es un grafo k - regular con 2 k − 1 vértices y 2 k − 2 k aristas.
El número cromático del grafo cúbico plegado de dimensión k es dos cuando k es par (es decir, en este caso, el grafo es bipartito ) y cuatro cuando k es impar. [1] La circunferencia impar de un cubo plegado de dimensión impar es k , por lo que para un k impar mayor que tres, los grafos cúbicos plegados proporcionan una clase de grafos sin triángulos con número cromático cuatro y circunferencia impar arbitrariamente grande. Como grafo regular en distancias con circunferencia impar k y diámetro ( k − 1)/2, los cubos plegados de dimensión impar son ejemplos de grafos 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 doble cubierta pero no la doble cubierta bipartita . En este caso, el cubo plegado ya es bipartito . Los grafos de cubo plegado heredan de sus subgrafos hipercubicos la propiedad de tener un ciclo hamiltoniano , y de los hipercubos que los cubren doblemente la propiedad de ser un grafo transitivo de distancia . [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 grafo bipartito con igual número de vértices en cada lado de la bipartición, muy diferente de la relación casi dos a uno para la bipartición de un árbol binario completo. [4]
En computación paralela , los grafos cúbicos plegados se han estudiado como una topología de red potencial , como una 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 solo 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]