En teoría de grafos , el grafo de Holt o grafo de Doyle es el grafo semitransitivo más pequeño , es decir, el ejemplo más pequeño de un grafo transitivo por vértices y transitivo por aristas que no es también simétrico . [1] [2] Tales grafos no son comunes. [3] Recibe su nombre en honor a Peter G. Doyle y Derek F. Holt, quienes descubrieron el mismo grafo de forma independiente en 1976 [4] y 1981 [5] respectivamente.
El grafo 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 con 4 vértices conectados y un grafo con 4 aristas conectadas . Tiene un grosor de libro de 3 y un número de cola de 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 grafo de la derecha lo destaca, ya que carece de simetría reflexiva.
El polinomio característico del gráfico de Holt es
Galería
Referencias
- ^ Doyle, P. "Un gráfico de 27 vértices que es transitivo por vértices y transitivo por aristas, pero no transitivo por L". Octubre de 1998. [1]
- ^ Alspach, Brian ; Marušič, Dragan ; Nowitz, Lewis (1994), "Construcción de gráficos que son ½-transitivos", Journal of the Australian Mathematical Society, Serie A , 56 (3): 391–402, doi : 10.1017/S1446788700035564.
- ^ Jonathan L. Gross, Jay Yellen, Manual de teoría de grafos , CRC Press, 2004, ISBN 1-58488-090-2 , pág. 491.
- ^ Doyle, PG (1976), On Transitive Graphs , Tesis de grado, Harvard CollegeSegún cita MathWorld.
- ^ Holt, Derek F. (1981), "Un gráfico que es transitivo en los bordes pero no en los arcos", Journal of Graph Theory , 5 (2): 201–204, doi :10.1002/jgt.3190050210.
- ^ ab Weisstein, Eric W. "Doyle Graph". MundoMatemático .
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018
