En el campo matemático de la teoría de grafos , el grafo de Robertson o (4,5) -cage, es un grafo 4 regular no dirigido con 19 vértices y 38 aristas que llevan el nombre de Neil Robertson . [2] [3]
Gráfico de Robertson | |
---|---|
Lleva el nombre de | Neil Robertson |
Vértices | 19 |
Bordes | 38 |
Radio | 3 |
Diámetro | 3 |
Circunferencia | 5 |
Automorfismos | 24 ( D 12 ) |
Número cromático | 3 |
Índice cromático | 5 [1] |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Jaula hamiltoniana |
Tabla de gráficos y parámetros |
El gráfico de Robertson es el único gráfico de jaula (4,5) y fue descubierto por Robertson en 1964. [4] Como gráfico de jaula, es el gráfico más pequeño de 4 regulares con una circunferencia de 5.
Tiene número cromático 3, índice cromático 5, diámetro 3, radio 3 y está conectado por 4 vértices y 4 por aristas . Tiene un grosor de libro 3 y un número de cola 2. [5]
El gráfico de Robertson es también un gráfico hamiltoniano que posee 5.376 ciclos hamiltonianos dirigidos distintos.
Propiedades algebraicas
El gráfico de Robertson no es un gráfico de vértice transitivo y su grupo de automorfismos completo es isomorfo al grupo diedro de orden 24, el grupo de simetrías de un dodecágono regular , que incluye tanto rotaciones como reflejos. [6]
El polinomio característico del gráfico de Robertson es
Galería
El gráfico de Robertson como se dibujó en la publicación original.
El número cromático del gráfico de Robertson es 3.
El índice cromático del gráfico de Robertson es 5.
Referencias
- ^ Weisstein, Eric W. "Gráfico de clase 2" . MathWorld .
- ^ Weisstein, Eric W. "Gráfico de Robertson" . MathWorld .
- ^ Bondy, JA y Murty, teoría de gráficos USR con aplicaciones. Nueva York: Holanda Septentrional, pág. 237, 1976.
- ^ Robertson, N. "El gráfico más pequeño de circunferencia 5 y valencia 4". Toro. Amer. Matemáticas. Soc. 70, 824-825, 1964.
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018
- ^ Geoffrey Exoo y Robert Jajcay, Encuesta dinámica de jaulas, Electr. J. Combin. 15 de 2008.