Grev Hoffman

Hoffman-grafen er en 4-regulær graf med 16 hjørner og 32 kanter, opdaget af Alan Hoffman [1] og udgivet i 1963. Grafen er cospektral i forhold til hyperkubegrafen Q 4 [2] [3] .

Hoffman-grafen deler mange egenskaber med hyperkuben Q 4 - begge er Hamiltonske og har kromatisk nummer 2, kromatisk indeks 4, omkreds 4 og diameter 4. Grafen er også 4-vertex-forbundet og 4-kant-forbundet . Imidlertid er radius af Hoffman-grafen 3, i modsætning til hyperkuben Q 4 (hvis radius er 4) [1] . Hoffmann-grafen er ikke afstandsregulær . Grafen har bogtykkelse 3 og antal køer 2 [4] .

Algebraiske egenskaber

Hoffman-grafen er ikke vertex-transitiv , og dens fulde automorfigruppe er en gruppe af orden 48 isomorf i forhold til det direkte produkt af den symmetriske gruppe S4 og den cykliske gruppe Z / 2Z .

Hoffman-grafens karakteristiske polynomium er

hvilket gør det til en heltalsgraf — en graf, hvis spektrum udelukkende består af heltal. Dette er det samme spektrum som det for hyperkuben Q 4 .

Galleri

• Den Hoffman Hamiltonske greve .

• Hoffman-grafens kromatiske tal er 2.

• Hoffman-grafens kromatiske indeks er 4.

Noter

1. ↑ 1 2 Weisstein, Eric W. Hoffman graf  (engelsk) på Wolfram MathWorld- webstedet .
2. ↑ Hoffman AJ On the Polynomial of a Graph  // Amer. Matematik. Månedlige. - 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. Engineering Lineære Layouts med SAT. - Universitetet i Tübingen, 2018. - (Kandidatspeciale).