En el campo matemático de la teoría de grafos , el gráfico de Hoffman es un gráfico regular de 4 con 16 vértices y 32 aristas descubierto por Alan Hoffman . [2] Publicado en 1963, es coespectral al gráfico de hipercubo Q 4 . [3] [4]
El gráfico 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, perímetro 4 y diámetro 4. También es un gráfico conectado por 4 vértices y un gráfico conectado por 4 aristas . Sin embargo, no es regular a distancia . Tiene grosor de libro 3 y número de cola 2. [5]
El grafo de Hoffman no es un grafo transitivo de vértice 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 .
convirtiéndolo en un gráfico integral, un gráfico cuyo espectro consiste completamente en números enteros. Es el mismo espectro que el hipercubo Q 4 .