En el campo matemático de la teoría de grafos , el grafo de Benson o de 12 jaulas de Tutte [1] es un grafo regular de 3 caras con 126 vértices y 189 aristas. Recibe su nombre en honor a WT Tutte . [2]
La jaula 12 de Tutte es la única jaula (3-12) (secuencia A052453 en la OEIS ). Fue descubierta por CT Benson en 1966. [3] Tiene número cromático 2 ( bipartito ), índice cromático 3, circunferencia 12 (como una jaula 12) y diámetro 6. Se sabe que su número de cruce es menor que 165, véase Wolfram MathWorld. [4] [5]
La jaula de 12 de Tutte es un grafo hamiltoniano cúbico y se puede definir mediante la notación MCF [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17] 7 . [6]
Existen, salvo isomorfismo, precisamente dos hexágonos generalizados de orden (2,2), como lo demostraron Cohen y Tits. Se trata del hexágono de Cayley partido H(2) y su dual punto-línea. Es evidente que ambos tienen el mismo grafo de incidencia, que de hecho es isomorfo a la jaula de 12 de Tutte. [1]
La jaula 11 de Balaban se puede construir por escisión de la jaula 12 de Tutte eliminando un pequeño subárbol y suprimiendo los vértices resultantes de grado dos. [7]
El grupo de automorfismos de la jaula de 12 de Tutte es de orden 12.096 y es un producto semidirecto del grupo unitario especial proyectivo PSU(3,3) con el grupo cíclico Z /2 Z . [1] Actúa transitivamente sobre sus aristas pero no sobre sus vértices, lo que lo convierte en un grafo semisimétrico , un grafo regular que es transitivo sobre aristas pero no sobre vértices . De hecho, el grupo de automorfismos de la jaula de 12 de Tutte conserva las partes bipartitas y actúa primitivamente sobre cada parte. Dichos grafos se denominan grafos biprimitivos y solo existen cinco grafos biprimitivos cúbicos; se denominan grafos de Iofinova-Ivanov y son de orden 110, 126, 182, 506 y 990. [8]
Se conocen todos los grafos cúbicos semisimétricos de hasta 768 vértices. Según Conder , Malnič, Marušič y Potočnik, el grafo de Tutte de 12 jaulas es el único grafo cúbico semisimétrico de 126 vértices y es el quinto grafo cúbico semisimétrico más pequeño posible después del grafo de Gray , el grafo de Iofinova-Ivanov de 110 vértices , el grafo de Ljubljana y un grafo de 120 vértices con circunferencia 8. [9]
El polinomio característico de la jaula 12 de Tutte es
Es el único grafo con este polinomio característico, por lo tanto, la jaula de 12 está determinada por su espectro .
