Greve Hoffman
| Greve Hoffman | |
|---|---|
| Döpt efter | Alan Hoffman |
| Toppar | 16 |
| revben | 32 |
| Radie | 3 |
| Diameter | fyra |
| Omkrets | fyra |
| Kromatiskt nummer | 2 |
| Kromatiskt index | fyra |
| Egenskaper |
Hamiltonsk tvådelad perfekt Euler |
| boktjocklek | 3 |
| Antal köer | 2 |
| Mediafiler på Wikimedia Commons | |
Hoffman-grafen är en 4-regelbunden graf med 16 hörn och 32 kanter, upptäckt av Alan Hoffman [1] och publicerad 1963. Grafen är kospektral till hyperkubgrafen Q 4 [2] [3] .
Hoffman-grafen delar många egenskaper med hyperkuben Q 4 - båda är Hamiltonska och har kromatiskt nummer 2, kromatiskt index 4, omkrets 4 och diameter 4. Grafen är också 4-vertex-ansluten och 4-kant-ansluten . Radien för Hoffman-grafen är dock 3, till skillnad från hyperkuben Q 4 (vars radie är 4) [1] . Hoffmann-grafen är inte avståndsregelbunden . Grafen har boktjocklek 3 och antal köer 2 [4] .
Algebraiska egenskaper
Hoffman-grafen är inte vertextransitiv och dess fullständiga automorfismgrupp är en grupp av ordningen 48 isomorf till den direkta produkten av den symmetriska gruppen S4 och den cykliska gruppen Z / 2Z .
Det karakteristiska polynomet i Hoffman-grafen är
,
vilket gör det till en heltalsgraf — en graf vars spektrum helt består av heltal. Detta är samma spektrum som det för hyperkuben Q 4 .
Galleri
-
Hoffman Hamiltonian greve .
-
Hoffman-grafens kromatiska tal är 2.
-
Det kromatiska indexet för Hoffman-grafen är 4.
Anteckningar
- ↑ 1 2 Weisstein, Eric W. Hoffman graf (engelska) på Wolfram MathWorld- webbplatsen .
- ↑ Hoffman AJ On the Polynomial of a Graph // Amer. Matematik. En gång i månaden. - 1963. - T. 70 . - S. 30-36 .
- ↑ van Dam ER, Haemers WH Spectral Characterizations of Some Distance-Regular Graphs // J. Algebraic Combin .. - 2003. - T. 15 . - S. 189-202 .
- ↑ Jessica Wolz. Tekniska linjära layouter med SAT. - Universitetet i Tübingen, 2018. - (Masteruppsats).