| Thatta-Coxeter grófja | |
|---|---|
| Valaki után elnevezve |
William Tutt Harold Coxeter |
| Csúcsok | harminc |
| borda | 45 |
| Átmérő | négy |
| Heveder | nyolc |
| Automorfizmusok | 1440 (Aut(S 6 )) |
| Kromatikus szám | 2 |
| Kromatikus index | 3 |
| Tulajdonságok |
köbös
távolság-tranzitív |
A Tutt-Coxeter gráf ( Tutt 8 cellás is ) egy 3 szabályos gráf , 30 csúcsgal és 45 éllel. Az egyetlen legkisebb köbös gráf 8-as kerülettel a cella és Moore gráf . Kétrészes , és egy W 2 általánosított négyszög Levi - gráfjaként szerkeszthető ( Cremona-Richmond konfigurációként ismert ). Nevét William Thomas Tuttról és Harold Coxeterről kapta . William Tutte találta ( Tutte 1947 ), de a geometriai kombinációhoz való viszonyát mindkét szerző egy pár közös dolgozatban vizsgálja ( Tutte, 1958 , Coxeter (a), 1958 ).
Egyike a tizenhárom köbméteres távolságszabályos gráfnak [1] .
A Tutt-Coxeter gráf egy különösen egyszerű kombinatorikus felépítését Coxeter javasolta ( Coxeter (b) 1958 ), és D. D. Sylvester korai munkásságán ( Sylvester 1844 ) alapul: hat elemből álló halmazt alkotunk (ezek például a az a, b, c, d, e, f betűk); Sylvester a ketteseket 15 rendezetlen elempárként határozta meg: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df vagy ef . Halmazokat is definiált - az elemek három kettesre való felosztását: (ab, cd, ef); (ab, ce, df); (ab, vö, de); (ac, bd, ef); (ac, be, df); (ac, bf, de); (ad, bc, ef); (ad, be, vö); (ad, bf, ce); (ae, bc, df); (ae, bd, cf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, be, cd). Minden készlet 3 2-t tartalmaz, és mindegyik 2 3 készlethez tartozik. A Tutta-Coxeter gráf olyan gráfnak tekinthető, amelyben minden csúcs egy 2-nek és egy 2-es halmaznak felel meg – minden halmazhoz egy csúcs, és minden halmazt élek kötnek össze a benne lévő három 2-vel.
Ezen konstrukció alapján Coxeter megmutatta, hogy a Tutt-Coxeter gráf szimmetrikus . 1440 gráf automorfizmusa van , amelyek a hatelemes permutációs csoport automorfizmusaival azonosíthatók ( Coxeter(b) 1958 ). Ennek a csoportnak a belső automorfizmusai hat elem permutációinak felelnek meg, amelyekből morfémákat és halmazokat határozunk meg. Ezek a permutációk úgy hatnak a Tutte-Coxeter gráfra, hogy permutálják a csúcsokat a kétrészes gráf egyes részein, és az egyes részeket halmazként tartják meg. Ezen kívül külső automorfizmusokA permutációs csoportok felcserélik a kétrészes gráf részeit. Amint azt Coxeter megmutatta, a Tutt-Coxeter gráfban minden öt élig tartó út ekvivalens bármely más ilyen útvonallal (vagyis ezeket az automorfizmusok valamelyikével fordítják át egyikről a másikra).
A Tutt-Coxeter gráf metszéspontjainak száma 13.
A Tutte-Coxeter gróf kromatikus száma 2.
a Tutt-Coxeter gráf kromatikus indexe 3.