En el campo matemático de la teoría de grafos , el grafo de Harries o la jaula de Harries (3-10) es un grafo 3- regular no dirigido con 70 vértices y 105 aristas. [1]
Gráfico de Harries | |
---|---|
Vértices | 70 |
Bordes | 105 |
Radio | 6 |
Diámetro | 6 |
Circunferencia | 10 |
Automorfismos | 120 ( S 5 ) |
Número cromático | 2 |
Índice cromático | 3 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Hamiltoniano sin triángulos de jaula cúbica |
Tabla de gráficos y parámetros |
El gráfico de Harries tiene número cromático 2, índice cromático 3, radio 6, diámetro 6, circunferencia 10 y es hamiltoniano . También es un gráfico cúbico no plano no plano de 3 vértices conectados y 3 aristas . Tiene un grosor de libro 3 y un número de cola 2. [2]
El polinomio característico del gráfico de Harries es
Historia
En 1972, AT Balaban publicó un gráfico de jaula (3-10) , un gráfico cúbico que tiene la menor cantidad posible de vértices para la circunferencia 10. [3] Fue la primera jaula (3-10) descubierta, pero no fue la única. . [4]
O'Keefe y Wong dieron la lista completa de jaulas (3-10) y la prueba de minimidad en 1980. [5] Existen tres gráficas distintas de jaulas (3-10): la jaula Balaban de 10 , la Gráfico de Harries y gráfico de Harries-Wong . [6] Además, el gráfico de Harries-Wong y el gráfico de Harries son gráficos cospectrales .
Galería
El número cromático del gráfico de Harries es 2.
El índice cromático del gráfico de Harries es 3.
Dibujo alternativo del gráfico de Harries.
Referencias
- ^ Weisstein, Eric W. "Gráfico de Harries" . MathWorld .
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018
- ^ EN Balaban, Un gráfico trivalente de circunferencia diez, J. Combin. Teoría Ser. B 12, 1-5. 1972.
- ^ Pisanski, T .; Boben, M .; Marušič, D .; y Orbanić, A. "Las configuraciones generalizadas de Balaban". Preimpresión. 2001. [1] .
- ^ M. O'Keefe y PK Wong, Un gráfico más pequeño de circunferencia 10 y valencia 3, J. Combin. Teoría Ser. B 29 (1980) 91-105.
- ^ Bondy, JA y Murty, teoría de gráficos USR con aplicaciones. Nueva York: Holanda Septentrional, pág. 237, 1976.