Gráfico de Clebsch | |
Representación del gráfico de Clebsch | |
Número de vértices | dieciséis |
---|---|
Numero de aristas | 40 |
Distribución de titulaciones | 5- regular |
Rayo | 2 |
Diámetro | 2 |
Malla | 4 |
Automorfismos | 1.920 |
Número cromático | 4 |
Índice cromático | 5 |
Propiedades |
Hamiltonian Cayley muy consistente |
El gráfico de Clebsch es, en teoría de grafos , un gráfico de 5 regulares con 16 vértices y 40 aristas. Fue nombrado así por su conexión con la superficie cuártica (en) descubierta por Alfred Clebsch en 1868. También se conoce como el gráfico de Greenwood-Gleason , debido al trabajo de Robert E. Greenwood y Andrew Gleason en 1955.
Podemos construir el gráfico de Clebsch conectando por ocho nuevos bordes los vértices opuestos de un hipercubo en cuatro dimensiones (es decir los vértices a una distancia de cuatro entre sí).
Otra construcción es fusionar los vértices opuestos del hipercubo en cinco dimensiones (por lo tanto, los vértices a una distancia de cinco entre sí).
La construcción histórica es la siguiente:
También obtenemos el gráfico de Clebsch al representar los elementos del campo finito GF (16) por vértices y al conectarlos cuando su diferencia en GF (16) es un número cúbico .
El gráfico de Clebsch es un gráfico de parámetros muy regular .
El diámetro de la gráfica de Clebsch, la excentricidad máxima de sus vértices, es 2, su radio , la excentricidad mínima de sus vértices, es 2 y su malla , la longitud de su ciclo más corto , es 4, por lo que es una gráfica sin un triángulo . Es un grafo conectado a 5 vértices y un grafo conectado a 5 aristas , es decir que está conectado y que para desconectarlo se debe privar de al menos 5 vértices o 5 aristas.
El gráfico de Clebsch también es un gráfico no plano , un gráfico no euleriano y un hamiltoniano .
El número cromático del gráfico de Clebsch es 4. Es decir que es posible colorearlo con 4 colores para que dos vértices conectados por una arista sean siempre de diferentes colores pero este número es mínimo. No hay 3 colores válidos del gráfico.
El índice cromático del gráfico de Clebsch es 5. Por lo tanto, hay una coloración de 5 en los bordes del gráfico, de modo que dos bordes incidentes en el mismo vértice son siempre de colores diferentes. Este número es mínimo.
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.
El grupo de automorfismo del gráfico de Clebsch es del orden de 1 920. Es isomorfo al grupo de Coxeter D 5 . Este grupo de automorfismos actúa de forma transitiva sobre el conjunto de vértices del gráfico de Clebsch, convirtiéndolo en un gráfico de vértice transitivo .
El polinomio característico de la matriz de adyacencia de la gráfica Clebsch es: . Solo admite raíces enteras. Por tanto, el gráfico de Clebsch es un gráfico integral , un gráfico cuyo espectro se compone de números enteros.
El gráfico complementario del gráfico de Clebsch es un gráfico de 10 regulares. También es muy consistente. Este es el gráfico de medio hipercubo construido a partir del hipercubo de 5 dimensiones ( penteracto ). Para construirlo conectamos los vértices que están a una distancia 2 en el hipercubo; esto da dos gráficos isomorfos de los cuales mantenemos solo uno de los dos.
Es este grafo de 10 regulares, con 16 vértices y 80 aristas que algunos autores como JJ Seidel (en 1968) o Andries Brouwer denominan “grafo de Clebsch”. El gráfico descrito por Clebsch un siglo antes, en su artículo de 1868, es sin embargo el gráfico de 5 regulares.
Sea cualquier vértice del gráfico de Clebsch. El subgrafo inducido en los 10 vértices que no son vecinos de es el gráfico de Petersen .