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