En el campo matemático de la teoría de grafos , el grafo de Foster es un grafo regular bipartito 3 con 90 vértices y 135 aristas. [1]
Fomentar gráfico | |
---|---|
![]() El gráfico de Foster | |
Lleva el nombre de | Ronald Martin Foster |
Vértices | 90 |
Bordes | 135 |
Radio | 8 |
Diámetro | 8 |
Circunferencia | 10 |
Automorfismos | 4320 |
Número cromático | 2 |
Índice cromático | 3 |
Número de cola | 2 |
Propiedades | Cúbico bipartito simétrico hamiltoniano distancia-transitivo |
Tabla de gráficos y parámetros |
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 de 3 vértices conectados y 3 bordes conectados . Tiene la cola número 2 y el límite superior del grosor del libro es 4. [2]
Todos los cúbicos gráficos distancia regular son conocidos. [3] El gráfico de Foster es uno de los 13 gráficos de este tipo. Es el único gráfico 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] Se puede construir como el gráfico de incidencia del espacio lineal parcial que es la única cubierta triple sin 8 gones del cuadrángulo generalizado GQ (2,2) . Lleva el nombre de RM Foster , cuyo censo Foster de gráficos cúbicos simétricos incluyó 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 de forma transitiva sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, la gráfica de Foster es simétrica . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier borde a cualquier otro borde. Según el censo de Foster , el gráfico de Foster, al que se hace referencia como F90A, es el único gráfico simétrico cúbico en 90 vértices. [7]
El polinomio característico del gráfico de Foster es igual a.
Galería
Fomentar el gráfico coloreado para resaltar varios ciclos.
El número cromático del gráfico de Foster es 2.
El índice cromático del gráfico de Foster es 3.
Referencias
- ^ Weisstein, Eric W. "Gráfico de fomento" . 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.
- ^ Gráficos cúbicos de distancia regular , 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
- ↑ Royle, G. F090A data [ enlace muerto permanente ]
- ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes hasta 768 vértices". J. Combin. Matemáticas. Combin. Computación. 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 algunas gráficas de distancia regular", Journal of Algebraic Combinatorics , 15 (2): 189-202, doi : 10.1023 / A: 1013847004932 , MR 1887234.
- Van Maldeghem, Hendrik (2002), "Diez geometrías excepcionales de gráficos regulares de distancia trivalente", Annals of Combinatorics , 6 (2): 209-228, doi : 10.1007 / PL00012587 , MR 1955521.