En la teoría de grafos , el gráfico de Holt o el gráfico de Doyle es el gráfico semitransitivo más pequeño , es decir, el ejemplo más pequeño de un gráfico transitivo de vértice y transitivo de borde que no es también simétrico . [1] [2] Tales gráficos no son comunes. [3] Lleva el nombre de Peter G. Doyle y Derek F. Holt, quienes descubrieron el mismo gráfico de forma independiente en 1976 [4] y 1981 [5] respectivamente.
El gráfico de Holt tiene un diámetro de 3, un radio de 3 y una circunferencia de 5, un número cromático de 3, un índice cromático de 5 y es hamiltoniano con 98 472 ciclos hamiltonianos distintos. [6] También es un grafo conectado por 4 vértices y conectado por 4 aristas . Tiene grosor de libro 3 y número de cola 3. [7]
Tiene un grupo de automorfismos de orden 54. [6] Este es un grupo más pequeño que el que tendría un grafo simétrico con el mismo número de vértices y aristas. El dibujo del gráfico de la derecha destaca esto, ya que carece de simetría de reflexión.