Grafo de Tutte-Coxeter

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
[editar datos en Wikidata]

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 ₂ (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).

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]​

1. ↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
2. ↑ Pegg, E. T.; Exoo, G. (2009). «Crossing Number Graphs». Mathematica Journal 11 (2). doi:10.3888/tmj.11.2-2. 
3. ↑ Exoo, G. «Rectilinear Drawings of Famous Graphs». 
4. ↑ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018