| Hrabě z Thatta-Coxeter | |
|---|---|
| Pojmenoval podle |
William Tutt Harold Coxeter |
| Vrcholy | třicet |
| žebra | 45 |
| Průměr | čtyři |
| obvod | osm |
| Automorfismy | 1440 (Aut(S 6 )) |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Vlastnosti |
krychlový
vzdálenostně tranzitivní |
Tutt-Coxeterův graf (také Tutt 8-cell ) je 3- regulární graf s 30 vrcholy a 45 hranami. Jediný nejmenší krychlový graf s obvodem 8 je buňkový a Mooreův graf . Je bipartitní a lze jej sestavit jako Leviho graf zobecněného čtyřúhelníku W 2 (známého jako Cremona-Richmondova konfigurace ). Pojmenovaný pro Williama Thomase Tutta a Harolda Coxetera . Nalezl ji William Tutte ( Tutte 1947 ), ale její vztah ke geometrické kombinaci zkoumají oba autoři ve dvojici společných prací ( Tutte, 1958 , Coxeter (a), 1958 ).
Je to jeden ze třinácti kubických vzdálenostně-regulárních grafů [1] .
Obzvláště jednoduchou kombinatorickou konstrukci Tutt-Coxeterova grafu navrhl Coxeter ( Coxeter (b) 1958 ) a vychází z rané práce D. D. Sylvestra ( Sylvester 1844 ): tvoříme množinu šesti prvků (např. písmena a, b, c, d, e, f); Sylvester definoval dvojky jako 15 neuspořádaných dvojic prvků: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df nebo ef. Definoval také množiny - rozdělení prvků na tři dvojky: (ab, cd, ef); (ab, ce, df); (ab, cf, de); (ac, bd, ef); (ac, be, df); (ac, bf, de); (ad, bc, ef); (ad, be, cf); (ad, bf, ce); (ae, bc, df); (ae, bd, cf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, be, cd). Každá sada obsahuje 3 2 a každá 2 patří do 3 sad. Tutta-Coxeterův graf si lze představit jako graf, ve kterém každý vrchol odpovídá 2 a množině 2 – jeden vrchol pro každou množinu a hrany spojují každou množinu se třemi 2, které obsahuje.
Na základě této konstrukce Coxeter ukázal, že Tutt-Coxeterův graf je symetrický . Má 1440 grafových automorfismů , které lze identifikovat s automorfismy šestiprvkové permutační grupy ( Coxeter(b) 1958 ). Vnitřní automorfismy této skupiny odpovídají permutacím šesti prvků, ze kterých definujeme morfémy a množiny. Tyto permutace působí na Tutte-Coxeterův graf permutací vrcholů na každé části bipartitního grafu, přičemž každá část zůstává jako množina. Navíc vnější automorfismypermutační skupiny zaměňují části bipartitního grafu. Jak ukázal Coxeter, jakákoli cesta až do pěti hran v Tutt-Coxeterově grafu je ekvivalentní jakékoli jiné takové cestě (to znamená, že jsou překládány z jedné na druhou pomocí jednoho z těchto automorfismů).
Počet průsečíků Tutt-Coxeterova grafu je 13.
Chromatické číslo hraběte Tutte-Coxetera je 2.
chromatický index Tutt-Coxeterova grafu je 3.