Conde hoffman

El gráfico de Hoffman es un gráfico de 4 regulares con 16 vértices y 32 aristas, descubierto por Alan Hoffman [1] y publicado en 1963. El gráfico es coespectral al gráfico de hipercubo Q 4 [2] [3] .

El gráfico de Hoffman comparte muchas propiedades 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. El gráfico también está conectado por 4 vértices y 4 aristas . Sin embargo, el radio del gráfico de Hoffman es 3, a diferencia del hipercubo Q 4 (cuyo radio es 4) [1] . El gráfico de Hoffmann no es de distancia regular . El gráfico tiene grosor de libro 3 y número de colas 2 [4] .

Propiedades algebraicas

El gráfico de Hoffman no es 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 .

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

lo que lo convierte en un gráfico de enteros, un gráfico cuyo espectro consiste completamente en números enteros. Este es el mismo espectro que el del hipercubo Q 4 .

Galería

• El conde hamiltoniano de Hoffman .

• El número cromático del gráfico de Hoffman es 2.

• El índice cromático del gráfico de Hoffman es 4.

Notas

1. ↑ 1 2 Gráfico Weisstein, Eric W. Hoffman  (inglés) en el sitio web Wolfram MathWorld .
2. ↑ Hoffman AJ Sobre el polinomio de un gráfico  // Amer. Matemáticas. Mensual. - 1963. - T. 70 . - S. 30-36 .
3. ↑ van Dam ER, Haemers WH Caracterizaciones espectrales de algunos gráficos regulares de distancia // J. Algebraic Combin .. - 2003. - T. 15 . - S. 189-202 .
4. ↑ Jessica Woltz. Ingeniería de Trazados Lineales con SAT. - Universidad de Tübingen, 2018. - (Tesis de Maestría).