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 regular de 3 con 30 vértices y 45 aristas. Como el único grafo cúbico más pequeño de circunferencia 8, es una jaula y un grafo de Moore . Es bipartito y se puede construir como el grafo de Levi del cuadrángulo generalizado W 2 (conocido como la configuración de Cremona-Richmond ). El grafo lleva el nombre de William Thomas Tutte y HSM Coxeter ; fue descubierto por Tutte (1947) pero 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 cúbicos de distancia regular. [1] El de Tutte-Coxeter es uno de los 13 grafos de este tipo.
Tiene número de cruce 13, [2] [3] grosor de libro 3 y número de cola 2. [4]
El grafo de Tutte-Coxeter es el grafo bipartito de Levi que conecta los 15 emparejamientos perfectos de un grafo completo de 6 vértices K 6 con sus 15 aristas, como lo describió Coxeter (1958b), basándose en el trabajo de Sylvester (1844). Cada vértice corresponde a una arista o un emparejamiento perfecto, y los vértices conectados representan la estructura de incidencia entre aristas y emparejamientos.
Basándose en 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 la permutación de los seis vértices del grafo K 6 ; estas permutaciones actúan sobre el grafo de Tutte-Coxeter permutando los vértices de 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 demostró Coxeter, cualquier camino de hasta cinco aristas en el grafo de Tutte-Coxeter es equivalente a cualquier otro camino de este tipo por uno de estos automorfismos.
Este grafo es el edificio esférico asociado al grupo simpléctico (existe un isomorfismo excepcional entre este grupo y el grupo simétrico ). Más concretamente, es el grafo de incidencia de un cuadrángulo generalizado .
Concretamente, el grafo de Tutte-Coxeter se puede definir a partir de un espacio vectorial simpléctico de 4 dimensiones de la siguiente manera:
