Gráfico de Hoffman

En el campo matemático de la teoría de grafos , el grafo de Hoffman es un grafo 4-regular con 16 vértices y 32 aristas descubierto por Alan Hoffman . ^{[ 2 ]} Publicado en 1963, es coespectral al grafo hipercubo Q ₄ . ^{[ 3 ] [ 4 ]}

El grafo de Hoffman tiene muchas propiedades comunes con el hipercubo Q ₄ : 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 4-conexo por vértices y un grafo 4-conexo por aristas . Sin embargo, no es regular en distancia ni 1-planar . ^{[ 5 ]} Tiene grosor de libro 3 y número de cola 2. ^{[ 6 ]}

El grafo de Hoffmann no es un grafo transitivo en vértices y su grupo de automorfismos completo es un grupo de orden 48 isomorfo al producto directo del grupo simétrico S ₄ y el grupo cíclico Z /2 Z . A pesar de no ser transitivo en vértices ni en aristas, el grafo de Hoffmann sigue siendo 1-walk-regular (pero no distancia-regular ).

El polinomio característico del gráfico de Hoffman es igual a

${\displaystyle (x-4)(x-2)^{4}x^{6}(x+2)^{4}(x+4)}$

lo que lo convierte en un grafo integral , un grafo cuyo espectro consiste enteramente en números enteros. Es el mismo espectro que el hipercubo Q ₄ .

• 
  El grafo de Hoffman es hamiltoniano .
• 
  El número cromático del gráfico de Hoffman es  2.
• 
  El índice cromático del gráfico de Hoffman es  4.