| Greve af Thatta-Coxeter | |
|---|---|
| Opkaldt efter |
William Tutt Harold Coxeter |
| Toppe | tredive |
| ribben | 45 |
| Diameter | fire |
| Omkreds | otte |
| Automorfismer | 1440 (Aut(S 6 )) |
| Kromatisk tal | 2 |
| Kromatisk indeks | 3 |
| Ejendomme |
kubisk
distance-transitiv |
Tutt-Coxeter grafen (også Tutt 8-celle ) er en 3 - regulær graf med 30 hjørner og 45 kanter. Den eneste mindste kubiske graf med omkreds 8 er cellen og Moore-grafen . Den er todelt og kan konstrueres som Levi-grafen af en generaliseret firsidet W 2 (kendt som Cremona-Richmond-konfigurationen ). Opkaldt efter William Thomas Tutt og Harold Coxeter . Fundet af William Tutte ( Tutte 1947 ), men dens relation til den geometriske kombination er udforsket af begge forfattere i et par fælles artikler ( Tutte, 1958 , Coxeter (a), 1958 ).
Det er en af tretten kubiske afstand-regulære grafer [1] .
En særlig simpel kombinatorisk konstruktion af Tutt-Coxeter grafen blev foreslået af Coxeter ( Coxeter (b) 1958 ) og er baseret på D. D. Sylvesters tidlige arbejde ( Sylvester 1844 ): vi danner et sæt af seks elementer (f.eks. er disse bogstaverne a, b, c, d, e, f); Sylvester definerede toer som 15 uordnede par af elementer: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df eller ef. Han definerede også sæt - opdelinger af elementer i tre toere: (ab, cd, ef); (ab, ce, df); (ab, jf, de); (ac, bd, ef); (ac, være, df); (ac, bf, de); (ad, bc, ef); (ad, være, jf); (ad, bf, ce); (ae, bc, df); (ae, bd, jf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, være, cd). Hvert sæt indeholder 3 2'ere, og hver 2 hører til 3 sæt. En Tutta-Coxeter-graf kan opfattes som en graf, hvor hvert toppunkt svarer til en 2'er og et sæt 2'ere - et toppunkt for hvert sæt, og kanter forbinder hvert sæt med de tre 2'ere, det indeholder.
Baseret på denne konstruktion viste Coxeter, at Tutt-Coxeter grafen er symmetrisk . Den har 1440 grafiske automorfier , som kan identificeres med automorfier af seks-element permutationsgruppen ( Coxeter(b) 1958 ). Indre automorfier af denne gruppe svarer til permutationer af seks elementer, hvorfra vi definerer morfemer og mængder. Disse permutationer virker på Tutte-Coxeter-grafen ved at permutere hjørnerne på hver del af den todelte graf, og holder hver del som et sæt. Derudover ydre automorfierpermutationsgrupper bytter dele af en todelt graf. Som Coxeter viste, svarer enhver sti op til fem kanter i Tutt-Coxeter-grafen til enhver anden sådan sti (det vil sige, de er oversat fra den ene til den anden ved hjælp af en af disse automorfismer).
Antallet af skæringspunkter i Tutt-Coxeter-grafen er 13.
Det kromatiske tal på grev Tutte-Coxeter er 2.
det kromatiske indeks for Tutt-Coxeter grafen er 3.