En el campo matemático de la teoría de grafos , el grafo de Harries-Wong es un grafo regular no dirigido de 3 ejes con 70 vértices y 105 aristas. [1]
El grafo 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 grafo cúbico no plano con 3 vértices conexos y 3 aristas conexas . Tiene un grosor de libro de 3 y un número de cola de 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 la menor cantidad 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 minimalidad fueron dadas por O'Keefe y Wong en 1980. [5] Existen tres grafos de (3-10)-jaulas distintos: la jaula de 10 Balaban , el grafo de Harries y el grafo de Harries-Wong. [6] Además, el grafo de Harries-Wong y el grafo de Harries son grafos coespectrales .
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.
Las 8 órbitas 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
- ^ AT Balaban, Un gráfico trivalente de circunferencia diez, J. Combin. Theory 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. Theory Ser. B 29 (1980) 91–105.
- ^ Bondy, JA y Murty, Teoría de grafos USR con aplicaciones. Nueva York: North Holland, pág. 237, 1976.
