Hoffmanův graf - Hoffman graph

Hoffmanův graf
Hoffman graph.svg
Hoffmanův graf
Pojmenoval podleAlan Hoffman
Vrcholy16
Hrany32
Poloměr3
Průměr4
Obvod4
Automorfismy48 (Z/2Z × S.4)
Chromatické číslo2
Chromatický index4
Tloušťka knihy3
Číslo fronty2
VlastnostiHamiltonian[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 Q4.[3][4]

Hoffmanův graf má mnoho společných vlastností s hyperkrychlí Q4-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 S4 a cyklická skupina Z/2Z.

The charakteristický polynom Hoffmanova grafu se rovná

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

Galerie

Reference

  1. ^ Weisstein, Eric W. "Hamiltonovský graf". MathWorld.
  2. ^ Weisstein, Eric W. "Hoffmanův graf". MathWorld.
  3. ^ Hoffman, A. J. „O polynomu grafu“. Amer. Matematika. 70, 30-36, 1963, měsíčně.
  4. ^ van Dam, E. R. a Haemers, W. H. „Spektrální charakterizace některých grafů závislých na vzdálenosti“. J. Algebraická kombinace. 15, 189-202, 2003.
  5. ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018