Gráfico de Clebsch

En el campo matemático de la teoría de grafos , el grafo de Clebsch es uno de dos grafos complementarios de 16 vértices: un grafo 5-regular con 40 aristas y un grafo 10-regular con 80 aristas. El grafo de 80 aristas es el grafo del cubo dividido a la mitad de dimensión 5 ; Seidel (1968) lo denominó grafo de Clebsch ^{[ 2 ]} debido a su relación con la configuración de 16 líneas en la superficie cuártica descubierta en 1868 por el matemático alemán Alfred Clebsch . La versión de 40 aristas es el grafo del cubo plegado de dimensión 5 ; también se le conoce como grafo de Greenwood - Gleason por el trabajo de Robert E. Greenwood y Andrew M. Gleason ( 1955 ) , quienes lo utilizaron para evaluar el número de Ramsey R (3,3,3) = 17. ^{[ 3 ] [ 4 ] [ 5 ]}   

El grafo de cubo plegado de dimensión 5 (el grafo de Clebsch 5-regular) se puede construir añadiendo aristas entre pares de vértices opuestos en un grafo hipercubo de 4 dimensiones. (En un hipercubo de n dimensiones, un par de vértices son opuestos si el camino más corto entre ellos tiene n aristas). Alternativamente, se puede formar a partir de un grafo hipercubo de 5 dimensiones identificando ( o contrayendo) todos los pares de vértices opuestos.

Otra construcción, que conduce al mismo grafo, consiste en crear un vértice para cada elemento del campo finito GF(16), y conectar dos vértices mediante una arista siempre que la diferencia entre los dos elementos correspondientes del campo sea un cubo perfecto . ^{[ 6 ]}

El grafo de cubo dividido a la mitad de dimensión 5 (el grafo de Clebsch 10-regular) es el complemento del grafo 5-regular. También puede construirse a partir de los vértices de un hipercubo de 5 dimensiones, conectando pares de vértices cuya distancia de Hamming sea exactamente dos. Esta construcción es un ejemplo de la construcción de grafos de Frankl-Rödl . Produce dos subconjuntos de 16 vértices que no están conectados entre sí; ambos semicuadrados del hipercubo son isomorfos al grafo de Clebsch 10-regular. Dos copias del grafo de Clebsch 5-regular pueden producirse de la misma manera a partir de un hipercubo de 5 dimensiones, conectando pares de vértices cuya distancia de Hamming sea exactamente cuatro.

El grafo de Clebsch 5-regular es un grafo fuertemente regular de grado 5 con parámetros${\displaystyle (v,k,\lambda,\mu)=(16,5,0,2)}$. ^{[ 7 ] [ 8 ]} Su complemento, el grafo de Clebsch 10-regular, es por lo tanto también un grafo fuertemente regular, ^{[ 1 ] [ 4 ]} con parámetros${\displaystyle (16,10,6,6)}$.

El grafo de Clebsch 5-regular es hamiltoniano , no planar y no euleriano . Además, es 5 -conexo por vértices y 5 -conexo por aristas . El subgrafo inducido por los diez no vecinos de cualquier vértice en este grafo forma una copia isomorfa del grafo de Petersen .

Tiene un grosor de libro de 4 y un número de cola de 3. ^{[ 9 ]}

Las aristas del grafo completo K ₁₆ pueden particionarse en tres copias disjuntas del grafo de Clebsch 5-regular. Dado que el grafo de Clebsch es un grafo libre de triángulos , esto demuestra que existe una coloración de tres colores libre de triángulos para las aristas de K ₁₆ ; es decir, que el número de Ramsey R (3,3,3) que describe el número mínimo de vértices en un grafo completo sin una coloración de tres colores libre de triángulos es al menos 17. Greenwood y Gleason (1955) utilizaron esta construcción como parte de su demostración de que R (3,3,3)  =  17. ^{[ 5 ] [ 10 ]}

El grafo de Clebsch 5-regular puede colorearse con cuatro colores, pero no con tres: su conjunto independiente más grande tiene cinco vértices, insuficientes para particionar el grafo en tres clases de color independientes. Contiene como subgrafo inducido el grafo de Grötzsch , el grafo cuatricromático sin triángulos más pequeño , y todo subgrafo inducido cuatricromático del grafo de Clebsch es un supergrafo del grafo de Grötzsch. Más aún, todo grafo cuatricromático sin triángulos y sin camino inducido de longitud seis o más es un subgrafo inducido del grafo de Clebsch y un supergrafo inducido del grafo de Grötzsch. ^{[ 11 ]}

El grafo de Clebsch 5-regular es el grafo de Keller de dimensión dos, que forma parte de una familia de grafos utilizados para encontrar teselaciones de espacios euclidianos de alta dimensión mediante hipercubos , de modo que no haya dos que se encuentren cara a cara.

El grafo de Clebsch 5-regular se puede incrustar como un mapa regular en la variedad orientable de género 5, formando caras pentagonales; y en la superficie no orientable de género 6, formando caras tetragonales.

• 
  El grafo de Clebsch es hamiltoniano .
• 
  El número acromático del gráfico de Clebsch es  8.
• 
  El número cromático del gráfico de Clebsch es  4.
• 
  El índice cromático del gráfico de Clebsch es  5.
• 
  Construcción del grafo de Clebsch a partir de un grafo hipercubo .