Gráfico de cubo plegado

En teoría de grafos , un grafo de cubo plegado es un grafo no dirigido que se forma a partir de un grafo de hipercubo añadiéndole un emparejamiento perfecto que conecta pares opuestos de vértices del hipercubo.

El grafo de cubo plegado de dimensión k (que contiene 2k ^{− 1 vértices}   ) se puede formar añadiendo aristas entre pares opuestos de vértices en un grafo de hipercubo de dimensión k − 1. (En un hipercubo con 2n ^vértices , un par de vértices son opuestos si el camino más corto entre ellos tiene longitud n ). De forma equivalente, se puede formar a partir de un grafo de hipercubo (también) de dimensión k , que tiene el doble de vértices, identificando (o contrayendo) cada par de vértices opuestos.  

Un grafo de cubo plegado de dimensión k es un k - regular con 2k ^{− 1 vértices}   y ^{2k − 2k}   aristas .

El número cromático del grafo de cubo 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 k impar mayor que tres, los grafos de cubo plegado proporcionan una clase de grafos libres de triángulos con número cromático cuatro y circunferencia impar arbitrariamente grande. Como un grafo distancia-regular 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 del que 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 hipercubo la propiedad de tener un ciclo hamiltoniano , y de los hipercubos que los cubren doblemente la propiedad de ser un grafo transitivo en distancia . ^{[ 3 ]}

Cuando k es impar, el cubo plegado de dimensión k contiene como subgrafo un árbol binario completo con 2 ^k-1 − 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 proporción casi de dos a uno para la bipartición de un árbol binario completo. ^{[ 4 ]}  

• El grafo del cubo plegado de dimensión tres es un grafo completo K ₄ .
• El grafo de cubo plegado de dimensión cuatro es el grafo bipartito completo K _4,4 .
• El grafo del cubo plegado de dimensión cinco es el grafo de Clebsch .
• El grafo del cubo plegado de dimensión seis es el grafo de Kummer , es decir, el grafo de Levi de la configuración punto-plano de Kummer .

En computación paralela , los grafos de cubo plegado se han estudiado como una topología de red potencial , como alternativa al hipercubo. En comparación 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 la difusión de información en un cubo plegado. ^{[ 5 ]}

• Gráfico de cubo dividido por la mitad

• van Bon, John (2007), "Grafos transitivos de distancia primitivos finitos", European Journal of Combinatorics , 28 (2): 517– 532, doi : 10.1016/j.ejc.2005.04.014.
• Choudam, SA; Nandini, R. Usha (2004), "Árboles binarios completos en cubos plegados y mejorados", Networks , 43 (4): 266–272 , doi : 10.1002/net.20002 , S2CID 6448906 .
• Van Dam, Edwin; Haemers, Willem H. (2010), Una caracterización extraña de los grafos impares generalizados , CentER Discussion Paper Series No. 2010-47, vol. 2010–47 , doi : 10.2139/ssrn.1596575 , SSRN 1596575  .
• El-Amawy, A.; Latifi, S. (1991), "Propiedades y rendimiento de hipercubos plegados", IEEE Trans. Parallel Distrib. Syst. , 2 (1): 31– 42, Bibcode : 1991ITPDS...2...31E , doi : 10.1109/71.80187.
• Godsil, Chris (2004), Gráficos interesantes y sus colores , CiteSeerX 10.1.1.91.6390 .
• Varvarigos, E. (1995), "Algoritmos de enrutamiento eficientes para redes de cubos plegados", Actas de la 14.ª Conferencia Internacional de Phoenix sobre Computadoras y Comunicaciones , IEEE, págs. 143-151 , doi : 10.1109/PCCC.1995.472498 , ISBN  0-7803-2492-7, S2CID 62407778 .

• Weisstein, Eric W. , "Grafo de cubo plegado" , MathWorld