Contele Hoffman

Contele Hoffman
Numit după Alan Hoffman
Vârfurile 16
coaste 32
Rază 3
Diametru patru
Circumferinţă patru
Număr cromatic 2
Indicele cromatic patru
Proprietăți Hamiltonian
Bipartit
Perfect
Euler
grosimea cărții 3
Numărul de cozi 2
 Fișiere media la Wikimedia Commons

Graficul Hoffman este un grafic cu 4 regulate cu 16 vârfuri și 32 de muchii, descoperit de Alan Hoffman [1] și publicat în 1963. Graficul este cospectral cu graficul hipercub Q 4 [2] [3] .

Graficul Hoffman are multe proprietăți cu hipercubul Q 4 - ambele sunt hamiltoniene și au numărul cromatic 2, indicele cromatic 4, circumferința 4 și diametrul 4. Graficul este, de asemenea , conectat la 4 vârfuri și conectat la 4 muchii . Totuși, raza graficului Hoffman este 3, spre deosebire de hipercubul Q 4 (a cărui rază este 4) [1] . Graficul Hoffmann nu este regulat la distanță . Graficul are grosimea cărții 3 și numărul de cozi 2 [4] .

Proprietăți algebrice

Graficul Hoffman nu este tranzitiv la vârf și grupul său de automorfism complet este un grup de ordinul 48 izomorf la produsul direct al grupului simetric S 4 și al grupului ciclic Z /2 Z .

Polinomul caracteristic al graficului Hoffman este

,

ceea ce îl face un graf întreg — un graf al cărui spectru este format în întregime din numere întregi. Acesta este același spectru cu cel al hipercubului Q 4 .

Galerie

Note

  1. ↑ 1 2 Weisstein, Eric W. Hoffman graph  (engleză) pe site-ul Wolfram MathWorld .
  2. ↑ Hoffman AJ Despre polinomul unui grafic  // Amer. Matematică. Lunar. - 1963. - T. 70 . - S. 30-36 .
  3. ↑ van Dam ER, Haemers WH Spectral Characterizations of Some Distance-Regular Graphs // J. Algebraic Combin .. - 2003. - T. 15 . - S. 189-202 .
  4. ↑ Jessica Wolz. Proiectări liniare cu SAT. - Universitatea din Tübingen, 2018. - (Teză de master).