En el campo matemático de la teoría de grafos , el grafo de Hoffman es un grafo regular de 4 elementos con 16 vértices y 32 aristas descubierto por Alan Hoffman . [2] Publicado en 1963, es coespectral al grafo hipercubo Q 4 . [3] [4]
El grafo de Hoffman tiene muchas propiedades comunes con el hipercubo Q 4 —ambos son hamiltonianos y tienen número cromático 2, índice cromático 4, circunferencia 4 y diámetro 4. También es un grafo conexo por 4 vértices y un grafo conexo por 4 aristas . Sin embargo, no es regular en distancias . Tiene un grosor de libro 3 y un número de cola 2. [5]
El grafo de Hoffman no es un grafo transitivo por vértices y su grupo de automorfismos completo es un grupo de orden 48 isomorfo al producto directo del grupo simétrico S 4 y el grupo cíclico Z /2 Z . A pesar de no ser transitivo por vértices ni por aristas, el grafo de Hoffman sigue siendo regular en 1 recorrido (pero no regular en distancias ).
El polinomio característico del gráfico de Hoffman es igual a
convirtiéndolo en un gráfico integral , es decir, un gráfico cuyo espectro está formado exclusivamente por números enteros. Es el mismo espectro que el hipercubo Q 4 .
