Hispanopedia Wiki
Articulo de referencia

Gráfico de Foster

[[Bipartite graph|Bipartite]] [[symmetric graph|Symmetric]] [[Hamiltonian graph|Hamiltonian]] [[Distance-transitive graph|Distance-transitive]]"},"queue number":{"wt":"2"}},"i":...

Hispanopedia WikiContenido en espanolLectura gratuita

En el campo matemático de la teoría de grafos , el grafo de Foster es un grafo bipartito 3- regular con 90 vértices y 135 aristas. [ 1 ]

El grafo de Foster es hamiltoniano y tiene número cromático 2, índice cromático 3, radio 8, diámetro 8 y circunferencia 10. También es un grafo 3 -conexo por vértices y 3 -conexo por aristas . Tiene número de cola 2 y el límite superior del grosor del libro es 4. [ 2 ]

Se conocen todos los grafos cúbicos distancia-regulares . [ 3 ] El grafo de Foster es uno de los 13 grafos de este tipo. Es el único grafo distancia-transitivo con matriz de intersección {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}. [ 4 ] Se puede construir como el grafo de incidencia del espacio lineal parcial que es la única triple cubierta sin 8-gonos del cuadrilátero generalizado GQ (2,2) . Recibe su nombre de RM Foster , cuyo censo de Foster de grafos cúbicos simétricos incluyó este grafo.

La mitad bipartita del grafo de Foster es un grafo distancia-regular y un grafo localmente lineal . Es uno de un número finito de tales grafos con grado seis. [ 5 ]

Propiedades algebraicas

El grupo de automorfismos del grafo de Foster es un grupo de orden 4320. [ 6 ] Actúa transitivamente sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el grafo de Foster es un grafo simétrico . Posee automorfismos que transforman cualquier vértice en cualquier otro vértice y cualquier arista en cualquier otra arista. Según el censo de Foster , el grafo de Foster, denominado F90A, es el único grafo cúbico simétrico con 90 vértices. [ 7 ]

El polinomio característico del gráfico de Foster es igual a(incógnita−3)(incógnita−2)9(incógnita−1)18incógnita10(incógnita+1)18(incógnita+2)9(incógnita+3)(incógnita2−6)12{\displaystyle (x-3)(x-2)^{9}(x-1)^{18}x^{10}(x+1)^{18}(x+2)^{9}(x+3)(x^{2}-6)^{12}}.

Referencias

  1. ↑ Weisstein, Eric W. "Grafo de Foster" . MathWorld .
  2. ↑ Wolz, Jessica; Diseño de distribuciones lineales mediante SAT. Tesis de maestría, Universidad de Tubinga, 2018.
  3. ^ Brouwer, AE; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
  4. ↑ Grafos cúbicos regulares en distancia , A. Brouwer.
  5. ↑ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Grafos regulares de distancia de valencia 6 ya1=1{\displaystyle a_{1}=1}", Journal of Algebraic Combinatorics , 11 (2): 101– 134, doi : 10.1023/A:1008776031839 , MR 1761910 
  6. ↑ "Gráfico de Foster G-12" , Enciclopedia de Gráficos , consultado el 26 de febrero de 2024.
  7. ↑ Conder, M. y Dobcsányi, P. "Grafos simétricos trivalentes hasta 768 vértices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  • Biggs, NL ; Boshier, AG; Shawe-Taylor, J. (1986), "Cubic distance-regular graphs", Journal of the London Mathematical Society , 33 (3): 385–394 , doi : 10.1112/jlms/s2-33.3.385 , MR 0850954 .
  • Van Dam, Edwin R.; Haemers, Willem H. (2002), "Caracterizaciones espectrales de algunos grafos regulares a distancia", Journal of Algebraic Combinatorics , 15 (2): 189– 202, doi : 10.1023/A:1013847004932 , MR 1887234 .
  • Van Maldeghem, Hendrik (2002), "Diez geometrías excepcionales a partir de grafos regulares de distancia trivalente", Annals of Combinatorics , 6 (2): 209–228 , doi : 10.1007/PL00012587 , MR 1955521 , S2CID 195315348  .