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 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
Hoffmanův graf je Hamiltonian.
The chromatické číslo Hoffmanova grafu je 2.
The chromatický index Hoffmanova grafu je 4.
Reference
- ^ Weisstein, Eric W. "Hamiltonovský graf". MathWorld.
- ^ Weisstein, Eric W. "Hoffmanův graf". MathWorld.
- ^ Hoffman, A. J. „O polynomu grafu“. Amer. Matematika. 70, 30-36, 1963, měsíčně.
- ^ 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.
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018