Hrabě Gewirtz

hrabě Gewirtz

Některé vložení se 7násobnou symetrií. 8násobná nebo 14násobná symetrie není možná
Pojmenoval podle Allan Gevirtsa
Vrcholy 56
žebra 280
Průměr 2
obvod čtyři
Automorfismy 80640
Chromatické číslo čtyři
Vlastnosti Silně pravidelný
Hamiltonovský
trojúhelník bez
Vertex-tranzitivní
Hrana-tranzitivní
Vzdálenost-tranzitivní
 Mediální soubory na Wikimedia Commons

Gewirtzův graf  je silně pravidelný graf s 56 vrcholy a valenci 10. Graf je pojmenován po matematikovi Allanu Gewirtzovi, který graf popsal ve své disertační práci [1] .

Budova

Gewirzův graf lze sestavit následovně. Zvažte jediný Steinerův systém s 22 prvky a 77 bloky. Vyberme si libovolný prvek a uvažujme vrcholy 56 bloků, které nejsou spojeny s tímto prvkem. Dva bloky spojíme hranou, pokud se neprotínají.

Touto konstrukcí lze vložit Gewirtzův graf do Higman-Simsova grafu .

Vlastnosti

Charakteristickým polynomem Gewirtzova grafu je

Proto je graf celočíselný graf  — graf, jehož spektrum se skládá výhradně z celých čísel. Gewirtzův graf je zcela definován svým spektrem.

Číslo nezávislosti grafu je 16.

Poznámky

  1. ↑ Allan Gewirtz. Grafy s maximálním sudým obvodem . - City University of New York, 1967. - (Ph.D. disertační práce v matematice).

Literatura