En la teoría de grafos , un grafo de cubo plegado es un grafo no dirigido formado a partir de un grafo de hipercubo al agregarle una coincidencia perfecta que conecta pares opuestos de vértices de hipercubo.
Gráfico de cubo plegado | |
---|---|
Vértices | 2 n −1 |
Bordes | 2 n −2 n |
Diámetro | piso ( n / 2) |
Número cromático | 2 (para n pares ) o 4 (cuando son impares). |
Propiedades | Gráfico regular Hamiltoniano Distancia-transitivo . |
Tabla de gráficos y parámetros |
Construcción
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 contrayéndose) cada par opuesto de vértices.
Propiedades
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 del gráfico cúbico plegado de dimensión k es dos cuando k es par (es decir, en este caso, el gráfico 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 gráficos de cubos plegados proporcionan una clase de gráficos sin triángulos con un número cromático cuatro y una circunferencia impar arbitrariamente grande. Como gráfico de distancia regular con circunferencia k impar y diámetro ( k - 1) / 2, los cubos doblados 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, la dimensión- k cubo 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 subgráficos de hipercubo la propiedad de tener un ciclo hamiltoniano , y de los hipercubos que los cubren por partida doble la propiedad de ser un gráfico transitivo a 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 gráfico bipartito con igual número de vértices en cada lado de la bipartición, muy diferente de la relación de casi dos a uno para la bipartición de un árbol binario completo. [4]
Ejemplos de
- El gráfico de cubo plegado de dimensión tres es un gráfico completo K 4 .
- El gráfico de cubo plegado de dimensión cuatro es el gráfico bipartito completo K 4,4 .
- El gráfico de cubo plegado de dimensión cinco es el gráfico de Clebsch .
- El gráfico de cubo plegado de dimensión seis es el gráfico de Kummer , es decir, el gráfico de Levi de la configuración punto-plano de Kummer .
Aplicaciones
En computación paralela , los gráficos de cubos plegados se han estudiado como una topología de red potencial , como una 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 . Los algoritmos distribuidos eficientes (en relación con los de un hipercubo ) son conocidos por transmitir información en un cubo plegado. [5]
Ver también
Notas
- ^ Godsil (2004) proporciona una prueba y atribuye el resultado a Naserasr y Tardif.
- ^ Van Dam y Haemers (2010) .
- ↑ van Bon (2007) .
- ^ Choudam y Nandini (2004) .
- ^ El-Amawy y Latifi (1991) ; Varvarigos (1995) .
Referencias
- van Bon, John (2007), "Gráficos 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.
- Van Dam, Edwin; Haemers, Willem H. (2010), An Odd Characterization of the Generalized Odd Graphs , CentER Discussion Paper Series No. 2010-47, SSRN 1596575.
- El-Amawy, A .; Latifi, S. (1991), "Propiedades y rendimiento de los hipercubos plegados", IEEE Trans. Distribución paralela. Syst. , 2 (1): 31–42, doi : 10.1109 / 71.80187.
- Godsil, Chris (2004), Gráficos interesantes y sus coloraciones , CiteSeerX 10.1.1.91.6390.
- Varvarigos, E. (1995), "Algoritmos de enrutamiento eficientes para redes de cubos plegados", Proc. 14th Int. Phoenix Conf. sobre Computadoras y Comunicaciones , IEEE, págs. 143-151, doi : 10.1109 / PCCC.1995.472498.
enlaces externos
- Weisstein, Eric W. "Gráfico de cubo plegado" . MathWorld .