Gráfico bipartito 3-regular con 90 vértices y 135 aristas
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 conexo por 3 vértices y conexo por 3 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 regulares de distancia . [3] El grafo de Foster es uno de los 13 grafos de este tipo. Es el único grafo transitivo de distancia con matriz de intersección {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}. [4] Puede construirse como el grafo de incidencia del espacio lineal parcial que es la única triple cubierta sin 8-gonos del cuadrángulo generalizado GQ (2,2) . Recibe su nombre en honor a RM Foster , cuyo censo Foster de grafos cúbicos simétricos incluía este grafo.
La mitad bipartita del grafo de Foster es un grafo regular en distancia 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, sobre las aristas y sobre los arcos del grafo. Por tanto, el grafo de Foster es un grafo simétrico . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Según el censo de Foster , el grafo de Foster, referenciado como F90A, es el único grafo cúbico simétrico sobre 90 vértices. [7]
El polinomio característico del gráfico de Foster es igual a .
Galería
Referencias
- ^ Weisstein, Eric W. "Gráfico de Foster". MathWorld .
- ^ Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ Brouwer, AE; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
- ^ Distancia cúbica-gráficos regulares, A. Brouwer.
- ^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Gráficos regulares a distancia de valencia 6 y ", Journal of Algebraic Combinatorics , 11 (2): 101–134, doi : 10.1023/A:1008776031839 , MR 1761910
- ^ "Gráfico de Foster G-12", Enciclopedia de gráficos , consultado el 26 de febrero de 2024
- ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes de hasta 768 vértices". J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
- Biggs, NL; Boshier, AG; Shawe-Taylor, J. (1986), "Gráficos regulares de distancia cúbica", 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 en función de la 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.
