En el campo matemático de la teoría de grafos , el grafo de Harries-Wong es un grafo 3 regular no dirigido con 70 vértices y 105 aristas. [1]
Gráfico de Harries-Wong | |
---|---|
Vértices | 70 |
Bordes | 105 |
Radio | 6 |
Diámetro | 6 |
Circunferencia | 10 |
Automorfismos | 24 ( S 4 ) |
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-Wong 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-Wong es
Historia
En 1972, AT Balaban publicó un gráfico de jaula (3-10), un gráfico cúbico que tiene el menor número posible de vértices para una circunferencia de 10. [3] Fue la primera jaula (3-10) descubierta, pero no fue la única. . [4]
La lista completa de (3-10) jaulas y la prueba de minimidad fue dada por O'Keefe y Wong en 1980. [5] Existen tres gráficos distintos de (3-10) jaulas: el Balaban de 10 jaulas , el 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-Wong es 2.
El índice cromático del gráfico de Harries-Wong es 3.
Dibujo alternativo del gráfico de Harries-Wong.
Referencias
- ^ Weisstein, Eric W. "Gráfico de Harries-Wong" . 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.