En teoría de grafos , el gráfico de Holt o 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 aristas que no es además simétrico . [1] [2] Estos 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 diámetro 3, radio 3 y circunferencia 5, número cromático 3, índice cromático 5 y es hamiltoniano con 98,472 ciclos hamiltonianos distintos. [6] También es un gráfico conectado con 4 vértices y con 4 aristas . Tiene un grosor de libro 3 y una cola número 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 gráfico simétrico con el mismo número de vértices y aristas. El gráfico de la derecha resalta esto, 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 de vértice y transitivo de borde, pero no transitivo L". Octubre de 1998. [1]
- ^ Alspach, Brian ; Marušič, Dragan ; Nowitz, Lewis (1994), "Construcción de gráficos ½ transitivos", Revista de la Sociedad Matemática Australiana, 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. 491.
- ^ Doyle, PG (1976), Sobre gráficos transitivos , tesis de último año, Harvard College. Según lo citado por MathWorld.
- ^ Holt, Derek F. (1981), "Un gráfico que es transitivo de aristas pero no transitivo de arco", Journal of Graph Theory , 5 (2): 201–204, doi :10.1002/jgt.3190050210.
- ^ ab Weisstein, Eric W. "Doyle Graph". MundoMatemático .
- ^ Jessica Wolz, Ingeniería de diseños lineales con SAT . Tesis de maestría, Universidad de Tübingen, 2018
