En el campo matemático de la teoría de grafos , el gráfico de Robertson o (4,5)-jaula, es un gráfico no dirigido de 4 regulares con 19 vértices y 38 aristas que lleva el nombre de Neil Robertson . [2] [3]
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 de 4 regulares más pequeño con 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 por 4 aristas . Tiene un grosor de libro 3 y una cola número 2. [5]
El gráfico de Robertson también es un gráfico hamiltoniano que posee 5376 ciclos hamiltonianos dirigidos distintos.
El gráfico de Robertson es uno de los gráficos más pequeños con el número de policía 4. [6]
El gráfico de Robertson no es un gráfico transitivo de vértices y su grupo de automorfismo completo es isomorfo al grupo diédrico de orden 24, el grupo de simetrías de un dodecágono regular , que incluye tanto rotaciones como reflexiones. [7]
El polinomio característico del gráfico de Robertson es
