Hispanopedia Wiki
Articulo de referencia

Gráfico de Holt

[[Edge-transitive graph|Edge-transitive]] [[Half-transitive graph|Half-transitive]] [[Hamiltonian graph|Hamiltonian]] [[Eulerian graph|Eulerian]] [[Cayley graph]]"},"book thickn...

Hispanopedia WikiContenido en espanolLectura gratuita

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 en vértices y en aristas que no es simétrico . [ 1 ] [ 2 ] Estos grafos no son comunes. [ 3 ] Recibe su nombre de 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 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 grafo 4 -conexo por vértices y 4 -conexo por aristas . Tiene grosor de libro 3 y número de cola 3. [ 7 ] El grafo no es 1-planar . [ 8 ]

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 pone de manifiesto, ya que carece de simetría de reflexión.

El polinomio característico del gráfico de Holt es

(incógnita3−6incógnita+2)6(incógnita+2)4(incógnita−1)4(incógnita−4). {\displaystyle (x^{3}-6x+2)^{6}(x+2)^{4}(x-1)^{4}(x-4).\ }

Referencias

  1. ↑ Doyle, P. "Un grafo de 27 vértices que es transitivo en vértices y transitivo en aristas, pero no transitivo en L." Octubre de 1998.
  2. ↑ Alspach, Brian ; Marušič, Dragan ; Nowitz, Lewis (1994), "Construcción de grafos semitransitivos", Journal of the Australian Mathematical Society, Serie A , 56 (3): 391–402 , doi : 10.1017/S1446788700035564.
  3. ↑ Jonathan L. Gross, Jay Yellen, Manual de teoría de grafos , CRC Press, 2004, ISBN 1-58488-090-2, pág. 491.
  4. ↑ Doyle, PG (1976), Sobre grafos transitivos , Tesis de licenciatura, Harvard CollegeSegún cita MathWorld.
  5. ↑ Holt, Derek F. (1981), "Un grafo que es transitivo por aristas pero no transitivo por arcos", Journal of Graph Theory , 5 (2): 201– 204, doi : 10.1002/jgt.3190050210.
  6. 1 2 Weisstein, Eric W. "Doyle Graph" . MathWorld .
  7. ↑ Jessica Wolz, Diseño de distribuciones lineales mediante SAT . Tesis de maestría, Universidad de Tubinga, 2018.
  8. ↑ Pupyrev, Sergey (2025), "OOPS: Optimized One-Planarity Solver via SAT", en Dujmović, Vida; Montecchiani, Fabrizio (eds.), Proc. 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 357, pp. 14:1–14:19, doi : 10.4230/LIPIcs.GD.2025.14 , ISBN   978-3-95977-403-1.
Lecturas relacionadas
6 articulos
Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...{\displaystyle f(v_{1})=v_{2}.\ }Gráfico transitivo de vérticeEn el campo matemático de la teoría de grafos , un automorfismo es una permutación de los vértices de modo que las aristas se asignan a aristas y l...Gráfico transitivo de aristasGráfico transitivo de aristasEn el campo matemático de la teoría de grafos , un grafo transitivo de aristas es un grafo G tal que, dadas dos aristas e 1 y e 2 de G , existe un ...Gráfico simétricoGráfico simétricoEn el campo matemático de la teoría de grafos , un grafo G es simétrico (o arco-transitivo ) si, dados dos pares de vértices adyacentes u 1 — v 1 y...Diámetro (teoría de grafos)Diámetro (teoría de grafos)En teoría de grafos , el diámetro de un grafo conexo no dirigido es la distancia máxima entre dos de sus vértices. Es decir, es el diámetro de un c...El gráfico de Petersen tiene una circunferencia de 5Circunferencia (teoría de grafos)En teoría de grafos , la circunferencia de un grafo no dirigido es la longitud del ciclo más corto contenido en el grafo. [1] Si el grafo no contie...