Hispanopedia Wiki
Articulo de referencia

Gráfico de Harries

[[Cage (graph theory)|Cage]] [[Triangle-free graph|Triangle-free]] [[Hamiltonian graph|Hamiltonian]]"},"book thickness":{"wt":"3"},"queue number":{"wt":"2"}},"i":0}}]}"> En el c...

Hispanopedia WikiContenido en espanolLectura gratuita

En el campo matemático de la teoría de grafos , el grafo de Harries o jaula de Harries (3-10) es un grafo no dirigido 3 - regular con 70 vértices y 105 aristas. [ 1 ]

El grafo 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 grafo cúbico no planar , con 3 vértices conectados y 3 aristas conectadas . Tiene grosor de libro 3 y número de cola 2. [ 2 ]

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

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

Historia

En 1972, AT Balaban publicó un grafo de jaula (3-10) , un grafo cúbico que tiene la menor cantidad de vértices posible para una circunferencia de 10. [ 3 ] Fue el primer grafo de jaula (3-10) descubierto, pero no era único. [ 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 (3-10)-jaulas distintos: la 10-jaula de 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 .

Referencias

  1. ↑ Weisstein, Eric W. "Gráfico de Harries" . MathWorld .
  2. ↑ Jessica Wolz, Diseño de distribuciones lineales mediante SAT . Tesis de maestría, Universidad de Tubinga, 2018.
  3. ↑ AT Balaban, Un grafo trivalente de circunferencia diez, J. Combin. Theory Ser. B 12, 1-5. 1972.
  4. ^ Pisanski, T.; Boben, M.; Marušič, D.; y Orbanić, A. "Las configuraciones generalizadas de Balaban". Preimpresión. 2001..
  5. ↑ 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.
  6. ↑ Bondy, JA y Murty, USR Teoría de grafos con aplicaciones. Nueva York: North Holland, pág. 237, 1976.