Grafo de Tutte-Coxeter

gráfico altamente simétrico con 30 vértices y 3 aristas por vértice

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

editar

Una 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

editar

Este 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

Referencias

editar
  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

Bibliografía

editar

Enlaces externos

editar