Gráfico de Gray
| Gráfico de Gray | |
|
Representación del gráfico de Gray. | |
| Número de vértices | 54 |
|---|---|
| Numero de aristas | 81 |
| Distribución de titulaciones | 3- regular |
| Rayo | 6 |
| Diámetro | 6 |
| Malla | 8 |
| Automorfismos | 1.296 |
| Número cromático | 2 |
| Índice cromático | 3 |
| Propiedades |
Hamiltoniano cúbico semi-simétrico |
El gráfico de Gray es, en teoría de grafos, un gráfico regular -3 con 54 vértices y 81 aristas.
Toma su nombre de Marion Cameron Gray, quien lo descubrió en 1932; fue publicado por primera vez por IZ Bouwer en 1968.
Propiedades
Propiedades generales
El diámetro del gráfico de Gray, la excentricidad máxima de sus vértices, es 6, su radio , la excentricidad mínima de sus vértices, es 6 y su malla , la longitud de su ciclo más corto , es 8. Esta es de 3 vértices- gráfico conectado y un gráfico conectado de 3 aristas , es decir, está conectado y para desconectarlo se debe privar de al menos 3 vértices o 3 aristas.
Colorante
El número cromático del gráfico de Gray es 2. Es decir que es posible colorearlo con 2 colores para que dos vértices conectados por una arista sean siempre de diferentes colores. Este número es mínimo.
El índice cromático del gráfico de Gray es 3. Por lo tanto, hay una coloración 3 de los bordes del gráfico, de modo que dos bordes incidentes al mismo vértice son siempre de colores diferentes. Este número es mínimo.
Propiedades algebraicas
El grupo de automorfismos del gráfico de Gray es un grupo de orden 1296. Actúa de manera transitiva sobre el conjunto de bordes del gráfico de Gray, convirtiéndolo en un gráfico de borde transitivo , es decir, un gráfico cuyos bordes juegan exactamente el mismo papel. Sin embargo, no actúa de forma transitiva en todos sus vértices. Dado que el gráfico de Gray es regular, es un ejemplo de un gráfico semi-simétrico : un gráfico transitivo de borde regular pero no transitivo de vértice. Es el gráfico cúbico más pequeño que satisface esta propiedad.
El polinomio característico de la matriz de adyacencia del gráfico gris es: . El gráfico de Gray está determinado únicamente por su espectro de gráfico , el conjunto de valores propios de su matriz de adyacencia .
Ver también
Vínculos internos
enlaces externos
- (en) Eric W. Weisstein , Gray Graph ( MathWorld )
- (es) Andries E. Brouwer , Gráfico de Gray
Referencias
- IZ Bouwer, edge An aim not vertex transitive cúbic graph , Boletín de la Sociedad Matemática Canadiense n. ° 11 (1968) p. 533-535.