Hoffmanův graf - Hoffman graph

Hoffmanův graf
Hoffmanův graf
Pojmenoval podle	Alan Hoffman
Vrcholy	16
Hrany	32
Poloměr	3
Průměr	4
Obvod	4
Automorfismy	48 (Z/2Z × S.4)
Chromatické číslo	2
Chromatický index	4
Tloušťka knihy	3
Číslo fronty	2
Vlastnosti	Hamiltonian[1] Bipartitní Perfektní Eulerian
Tabulka grafů a parametrů

V matematický pole teorie grafů, Hoffmanův graf je 4-běžný graf se 16 vrcholy a 32 hranami objevenými Alan Hoffman.^[2] Publikováno v roce 1963, je to cospectral k hyperkrychlový graf Q₄.^[3][4]

Hoffmanův graf má mnoho společných vlastností s hyperkrychlí Q₄-oba jsou Hamiltonian a mít chromatické číslo 2, chromatický index 4, obvod 4 a průměr 4. Je to také 4graf spojený s vrcholem a 4-hranový graf. Ale není vzdálenost-pravidelná. Má to tloušťka knihy 3 a číslo fronty 2.^[5]

Algebraické vlastnosti

Hoffmanův graf není a vrchol-tranzitivní graf a její úplná automorfická skupina je skupina řádu 48 isomorfní s přímý produkt z symetrická skupina S₄ a cyklická skupina Z/2Z.

The charakteristický polynom Hoffmanova grafu se rovná

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

dělat to integrální graf — Graf, jehož spektrum skládá se výhradně z celých čísel. Je to stejné spektrum jako hyperkrychle Q₄.

Galerie

• 

  Hoffmanův graf je Hamiltonian.

• 

  The chromatické číslo Hoffmanova grafu je 2.

• 

  The chromatický index Hoffmanova grafu je 4.

Reference