En el campo matemático de la teoría de grafos , el grafo de Horton o el grafo de Horton 96 es un gráfico 3- regular con 96 vértices y 144 aristas descubierto por Joseph Horton. [1] Publicado por Bondy y Murty en 1976, proporciona un contraejemplo a la conjetura de Tutte de que cada grafo bipartito cúbico de 3 conexiones es hamiltoniano . [2] [3]
Después del gráfico de Horton, se encontraron varios contraejemplos más pequeños de la conjetura de Tutte. Entre ellos se encuentran un gráfico de 92 vértices de Horton publicado en 1982, un gráfico de 78 vértices de Owens publicado en 1983 y los dos gráficos de Ellingham-Horton (54 y 78 vértices). [4] [5]
El primer gráfico de Ellingham-Horton fue publicado por Ellingham en 1981 y era del orden 78. [6] En ese momento, era el contraejemplo más pequeño conocido de la conjetura de Tutte. El segundo fue publicado por Ellingham y Horton en 1983 y era de orden 54. [7] En 1989, se descubrió el gráfico de Georges, el gráfico bipartito cúbico de tres conexiones no hamiltoniano más pequeño que se conoce actualmente, que contiene 50 vértices. [8]
Como gráfico cúbico no hamiltoniano con muchos ciclos largos, el gráfico de Horton proporciona un buen punto de referencia para los programas que buscan ciclos hamiltonianos. [9]
El gráfico de Horton tiene número cromático 2, índice cromático 3, radio 10, diámetro 10, circunferencia 6, grosor del libro 3 [10] y número de cola 2. [10] También es un gráfico conectado por 3 bordes .
El grupo de automorfismo de la gráfica de Horton es de orden 96 y es isomorfo a Z / 2 Z × Z / 2 Z × S 4 , el producto directo de los cuatro grupos de Klein y el grupo simétrico S 4 .