Gewirtzův graf - Gewirtz graph - Wikipedia

Gewirtzův graf
	Některá vložení se 7násobnou symetrií. Není možná 8násobná ani 14násobná symetrie.
Vrcholy	56
Hrany	280
Poloměr	2
Průměr	2
Obvod	4
Automorfismy	80,640
Chromatické číslo	4
Vlastnosti	Silně pravidelné; Hamiltonian; Bez trojúhelníků; Vrchol-tranzitivní; Edge-tranzitivní; Vzdálenost-tranzitivní.
	Tabulka grafů a parametrů

The Gewirtzův graf je silně pravidelný graf s 56 vrcholy a valencí 10. Je pojmenována po matematikovi Allanovi Gewirtzovi, který ve své disertační práci popsal graf.^[1]

Konstrukce

Gewirtzův graf lze sestrojit následovně. Zvažte jedinečný S(3, 6, 22) Steinerův systém, s 22 prvky a 77 bloky. Vyberte náhodný prvek a nechte vrcholy 56 bloků, které jej neobsahují. Dva bloky sousedí, když jsou disjunktní.

S touto konstrukcí lze graf Gewirtz vložit do Graf Higman – Sims.

Vlastnosti

The charakteristický polynom grafu Gewirtz je

{ displaystyle (x-10) (x-2) ^ {35} (x + 4) ^ {20}. ,}

Proto je to integrální graf. Graf Gewirtz je také určen jeho spektrem.

The číslo nezávislosti je 16.

Poznámky

^ Allan Gewirtz, Grafy s maximálním rovnoměrným obvodem, Ph.D. Disertační práce z matematiky, City University of New York, 1967.

Reference

Brouwer, Andries. „Graf Sims-Gewirtz“.
Weisstein, Eric W. „Gewirtzův graf“. MathWorld.

[1] Allan Gewirtz, Grafy s maximálním rovnoměrným obvodem, Ph.D. Disertační práce z matematiky, City University of New York, 1967.

[1]