En el campo matemático de la teoría de grafos , el grafo de Tutte-Coxeter o el grafo de ocho jaulas de Tutte o el de Cremona – Richmond es un grafo regular 3 con 30 vértices y 45 aristas. Como el único gráfico cúbico más pequeño de circunferencia 8, es una jaula y un gráfico de Moore . Es bipartito y se puede construir como el gráfico de Levi del cuadrángulo generalizado W 2 (conocido como configuración Cremona-Richmond ). El gráfico lleva el nombre de William Thomas Tutte yHSM Coxeter ; fue descubierto por Tutte (1947), pero ambos autores investigaron su conexión con las configuraciones geométricas en un par de artículos publicados conjuntamente (Tutte 1958; Coxeter 1958a).
Gráfico de Tutte-Coxeter | |
---|---|
Lleva el nombre de | WT Tutte H. SM Coxeter |
Vértices | 30 |
Bordes | 45 |
Radio | 4 |
Diámetro | 4 |
Circunferencia | 8 |
Automorfismos | 1440 (Aut (S 6 )) |
Número cromático | 2 |
Índice cromático | 3 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Gráfico de Moore de jaula cúbica Simétrico Distancia-regular Distancia-transitivo Bipartito |
Tabla de gráficos y parámetros |
Todos los cúbicos gráficos distancia regular son conocidos. [1] El Tutte-Coxeter es uno de los 13 gráficos de este tipo.
Tiene número de cruce 13, [2] [3] grosor de libro 3 y número de cola 2. [4]
Construcciones y automorfismos
Una construcción combinatoria particularmente simple del gráfico de Tutte-Coxeter se debe a Coxeter (1958b), basada en el trabajo de Sylvester (1844). En terminología moderna, tome una gráfica completa en 6 vértices K 6 . Tiene 15 aristas y también 15 combinaciones perfectas . Cada vértice del gráfico de Tutte-Coxeter corresponde a un borde o coincidencia perfecta del K 6 , y cada borde del gráfico de Tutte-Coxeter conecta un emparejamiento perfecto del K 6 a cada uno de sus tres bordes componentes. Por simetría, cada borde del K 6 pertenece a tres combinaciones perfectas. Por cierto, esta división de vértices en vértices de borde y vértices coincidentes muestra que el gráfico de Tutte-Coxeter es bipartito.
Con base en esta construcción, Coxeter mostró que el gráfico de Tutte-Coxeter es un gráfico simétrico ; tiene un grupo de 1440 automorfismos , que pueden identificarse con los automorfismos del grupo de permutaciones en seis elementos (Coxeter 1958b). Los automorfismos internos de este grupo corresponden a la permutación de los seis vértices del gráfico K 6 ; estas permutaciones actúan sobre el gráfico de Tutte-Coxeter permutando los vértices en cada lado de su bipartición mientras mantienen cada uno de los dos lados fijos como un conjunto. Además, los automorfismos externos del grupo de permutaciones intercambian un lado de la bipartición por el otro. Como mostró Coxeter, cualquier camino de hasta cinco aristas en el gráfico de Tutte-Coxeter es equivalente a cualquier otro camino por uno de esos automorfismos.
El gráfico de Tutte-Coxeter como edificio
Este gráfico es el edificio esférico asociado al grupo simpléctico (hay un isomorfismo excepcional entre este grupo y el grupo simétrico ). Más específicamente, es el gráfico de incidencia de un cuadrilátero generalizado .
Concretamente, el gráfico de Tutte-Coxeter se puede definir a partir de un espacio vectorial simpléctico de 4 dimensiones. encima como sigue:
- Los vértices son vectores distintos de cero o subespacios bidimensionales isotrópicos,
- hay un borde entre un vector v distinto de cero y un subespacio bidimensional isotrópico si y solo si .
Galería
El número cromático del gráfico de Tutte-Coxeter es 2.
El índice cromático del gráfico de Tutte-Coxeter es 3.
Referencias
- ^ Brouwer, AE; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
- ^ Pegg, ET ; Exoo, G. (2009). "Gráficos de números de cruce". Revista Mathematica . 11 (2). doi : 10.3888 / tmj.11.2-2 .
- ^ Exoo, G. "Dibujos rectilíneos de gráficos famosos" .
- ^ Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- Coxeter, HSM (1958a). "Los acordes de la cuádrica no reglada en PG (3,3)". Lata. J. Math . 10 : 484–488. doi : 10.4153 / CJM-1958-047-0 .
- Coxeter, HSM (1958b). "Doce puntos en PG (5,3) con 95040 autotransformaciones". Proceedings of the Royal Society A . 247 (1250): 279–293. doi : 10.1098 / rspa.1958.0184 . JSTOR 100667 . S2CID 121676627 .
- Sylvester, JJ (1844). "Investigaciones elementales en el análisis de agregación combinatoria" . Phil. Mag . Serie 3. 24 : 285-295. doi : 10.1080 / 14786444408644856 .
- Tutte, WT (1947). "Una familia de gráficos cúbicos". Proc. Cambridge Philos. Soc . 43 (4): 459–474. doi : 10.1017 / S0305004100023720 .
- Tutte, WT (1958). "Los acordes de la cuádrica no reglada en PG (3,3)". Lata. J. Math . 10 : 481–483. doi : 10.4153 / CJM-1958-046-3 .
enlaces externos
- François Labelle. "Modelo 3D de 8 jaulas de Tutte" .
- Weisstein, Eric W. "Levi Graph" . MathWorld .
- Exoo, G. "Dibujos rectilíneos de gráficos famosos". [1]