Grafo de Tutte-Coxeter
En el campo matemático de la teoría de grafos, el grafo de Tutte-Coxeter o grafo de ocho jaulas de Tutte o grafo de Cremona-Richmond es un grafo 3-regular con 30 vértices y 45 aristas. Como el único grafo cúbico más pequeño de cintura 8, es una jaula y un grafo de Moore. Es bipartito y se puede construir como el grafo de Levi del cuadrilátero generalizado W 2 (conocido como la configuración de Cremona-Richmond). Lleva el nombre de William Thomas Tutte y de H. S. M. Coxeter. Aunque fue descubierto por Tutte (1947), su conexión con las configuraciones geométricas fue investigada por ambos autores en un par de artículos publicados conjuntamente (Tutte 1958; Coxeter 1958a).
| Grafo de Tutte-Coxeter | ||
|---|---|---|
 | ||
| Nombre en honor a |
W. T. Tutte H. S. M. Coxeter | |
| Vértices | 30 | |
| Aristas | 45 | |
| Radio | 4 | |
| Diámetro | 4 | |
| Cintura | 8 | |
| Automorfismos | 1440 (Aut(S6)) | |
| Número cromático | 2 | |
| Índice cromático | 3 | |
| Propiedades |
Cúbico Jaula Grafo de Moore Simétrico Distancia-regular Distancia-transitivo Bipartito | |
Se conocen todos los grafos de distancia regular cúbicos.[1] El grafo de Tutte-Coxeter es uno de los 13 grafos de este tipo.
Tiene número de cruces 13,[2][3] espesor de libro 3 y número de colas 2.[4]
Construcciones y automorfismos
editarUna construcción combinatoria particularmente simple del grafo de Tutte-Coxeter se debe a Coxeter (1958b), basada en el trabajo de Sylvester (1844). En terminología moderna, se toma un grafo completo en 6 vértices K6, que tiene15 aristas y también 15 combinaciones perfectas. Cada vértice del grafo de Tutte-Coxeter corresponde a una arista o coincidencia perfecta de K6, y cada arista del grafo de Tutte-Coxeter conecta una coincidencia perfecta de K6 con cada una de sus tres aristas componentes. Por simetría, cada arista de K6 pertenece a tres coincidencias perfectas. Además, esta partición de vértices en vértices de arista y vértices coincidentes muestra que el grafo de Tutte-Coxeter es bipartito.
Sobre la base de esta construcción, Coxeter demostró que el grafo de Tutte-Coxeter es un grafo simétrico; tiene un grupo de 1440 automorfismos, que pueden identificarse con los automorfismos del grupo de permutaciones sobre seis elementos (Coxeter 1958b). Los automorfismos internos de este grupo corresponden a permutar los seis vértices del grafo K6; estas permutaciones actúan sobre el grafo de Tutte-Coxeter al permutar los vértices de cada lado de su bipartición mientras se mantienen fijos cada uno de los dos lados 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 grafo de Tutte-Coxeter es equivalente a cualquier otro camino por uno de esos automorfismos.
El gráfico de Tutte-Coxeter como edificio
editarEste grafo 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 grafo de incidencia de un cuadrilátero generalizado.
Concretamente, el grafo de Tutte-Coxeter se puede definir a partir de un espacio vectorial simpléctico de 4 dimensiones sobre como sigue:
- Los vértices son vectores distintos de cero o subespacios bidimensionales isotrópicos.
- Hay uns arista entre un vector v distinto de cero y un subespacio bidimensional isotrópico si y solo si .
Galería
editar-
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
editar- ↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
- ↑ Pegg, E. T.; Exoo, G. (2009). «Crossing Number Graphs». Mathematica Journal 11 (2). doi:10.3888/tmj.11.2-2.
- ↑ Exoo, G. «Rectilinear Drawings of Famous Graphs».
- ↑ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Bibliografía
editar- Coxeter, H. S. M. (1958a). «The chords of the non-ruled quadric in PG(3,3)». Can. J. Math. 10: 484-488. doi:10.4153/CJM-1958-047-0.
- Coxeter, H. S. M. (1958b). «Twelve points in PG(5,3) with 95040 self-transformations». Proceedings of the Royal Society A 247 (1250): 279-293. doi:10.1098/rspa.1958.0184.
- Sylvester, J. J. (1844). «Elementary researches in the analysis of combinatorial aggregation». Phil. Mag. Series 3 24: 285-295. doi:10.1080/14786444408644856.
- Tutte, W. T. (1947). «A family of cubical graphs». Proc. Cambridge Philos. Soc. 43 (4): 459-474. doi:10.1017/S0305004100023720.
- Tutte, W. T. (1958). «The chords of the non-ruled quadric in PG(3,3)». Can. J. Math. 10: 481-483. doi:10.4153/CJM-1958-046-3.
Enlaces externos
editar- François Labelle. «3D Model of Tutte's 8-cage».
- Weisstein, Eric W. «Levi Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- Exoo, G. "Rectilinear Drawings of Famous Graphs." [1]
Datos: Q3115542
