Gráfico bipartito de 3 regulares con 90 vértices y 135 aristas
En el campo matemático de la teoría de grafos , el gráfico de Foster es un gráfico bipartito de 3 regulares con 90 vértices y 135 aristas. [1]
El gráfico 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 gráfico conectado con 3 vértices y 3 bordes . Tiene la cola número 2 y el límite superior del grosor del libro es 4. [2]
Se conocen todas las gráficas cúbicas de distancia regular . [3] El gráfico de Foster es uno de los 13 gráficos de este tipo. Es el gráfico transitivo de distancia único 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 gráfico de incidencia del espacio lineal parcial que es la única cubierta triple sin 8 gónos del cuadrilátero generalizado GQ (2,2) . Lleva el nombre de RM Foster , cuyo censo Foster de gráficos simétricos cúbicos incluía este gráfico.
La mitad bipartita del gráfico de Foster es un gráfico de distancia regular y un gráfico localmente lineal . Es uno de un número finito de tales gráficos 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 tanto, la gráfica de Foster es una gráfica simétrica . 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 gráfico de Foster, denominado F90A, es el único gráfico simétrico cúbico de 90 vértices. [7]
El polinomio característico del gráfico de Foster es igual a .
Galería
Referencias
- ^ Weisstein, Eric W. "Fomentar gráfico". MundoMatemático .
- ^ Wolz, Jessica; Ingeniería de Trazados Lineales 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.
- ^ Gráficos regulares de distancia cúbica, A. Brouwer.
- ^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Gráficos de distancia regular de valencia 6 y ", Journal of Algebraic Combinatorics , 11 (2): 101–134, doi : 10.1023/A:1008776031839 , MR 1761910
- ^ Royle, G. Datos F090A [ enlace muerto permanente ]
- ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes de hasta 768 vértices". J. Combinar. Matemáticas. Combinar. Computadora. 40, 41-63, 2002.
- Biggs, Países Bajos; Boshier, AG; Shawe-Taylor, J. (1986), "Gráficos regulares de distancia cúbica", Revista de la Sociedad Matemática de Londres , 33 (3): 385–394, doi :10.1112/jlms/s2-33.3.385, SEÑOR 0850954.
- Van Dam, Edwin R.; Haemers, Willem H. (2002), "Caracterizaciones espectrales de algunos gráficos de distancia regulares", 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 gráficos regulares de distancia trivalente", Annals of Combinatorics , 6 (2): 209–228, doi :10.1007/PL00012587, MR 1955521, S2CID 195315348.
