En el campo matemático de la teoría de grafos , el grafo de Biggs-Smith es un grafo regular 3 con 102 vértices y 153 aristas. [1]
Gráfico de Biggs-Smith | |
---|---|
Vértices | 102 |
Bordes | 153 |
Radio | 7 |
Diámetro | 7 |
Circunferencia | 9 |
Automorfismos | 2448 ( PSL (2,17)) |
Número cromático | 3 |
Índice cromático | 3 |
Propiedades | Hamiltoniano cúbico simétrico a distancia regular |
Tabla de gráficos y parámetros |
Tiene número cromático 3, índice cromático 3, radio 7, diámetro 7 y circunferencia 9. También es un gráfico conectado a 3 vértices y un gráfico conectado a 3 aristas .
Todos los cúbicos gráficos distancia regular son conocidos. [2] El gráfico de Biggs-Smith es uno de los 13 gráficos de este tipo.
Propiedades algebraicas
El grupo de automorfismo del gráfico de Biggs-Smith es un grupo de orden 2448 [3] isomorfo al grupo lineal especial proyectivo PSL (2,17). Actúa de forma transitiva sobre los vértices, las aristas y los arcos del gráfico. Por lo tanto, la gráfica de Biggs-Smith 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 Biggs-Smith, al que se hace referencia como F102A, es el único gráfico simétrico cúbico en 102 vértices. [4]
El gráfico de Biggs-Smith también está determinado únicamente por su espectro de gráfico , el conjunto de valores propios de gráfico de su matriz de adyacencia . [5]
El polinomio característico del gráfico de Biggs-Smith es:.
Galería
El número cromático del gráfico de Biggs-Smith es 3.
El índice cromático del gráfico de Biggs-Smith es 3.
Dibujo alternativo del gráfico de Biggs-Smith.
Referencias
- ^ Weisstein, Eric W. "Gráfico de Biggs-Smith" . MathWorld .
- ^ Brouwer, AE ; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
- ↑ Royle, G. F102A 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.
- ^ ER van Dam y WH Haemers, caracterizaciones espectrales de algunos gráficos de distancia regular. J. Algebraic Combin. 15, páginas 189–202, 2003
- Sobre gráficos trivalentes, NL Biggs, DH Smith - Bulletin of the London Mathematical Society, 3 (1971) 155-158.