Tutte 12-bur
| Tutte 12-bur | |
|---|---|
 Tutte 12-bur
| |
| Döpt efter | WT Tutte |
| Vertices | 126 |
| Kanter | 189 |
| Radie | 6 |
| Diameter | 6 |
| Omkrets | 12 |
| Automorfismer | 12096 |
| Kromatiskt nummer | 2 |
| Kromatiskt index | 3 |
| Egenskaper |
Cubic Cage Hamiltonian Semi-symmetrisk Bipartite |
| Tabell över grafer och parametrar | |
Inom det matematiska området grafteorin är Tutte 12-buren eller Benson-grafen en 3- regelbunden graf med 126 hörn och 189 kanter uppkallad efter WT Tutte .
Tutte 12-buren är den unika (3-12) -buren (sekvens A052453 i OEIS ). Den upptäcktes av CT Benson 1966. Den har kromatiskt nummer 2 ( bipartit ), kromatiskt index 3, omkrets 12 (som en 12-bur) och diameter 6. Dess korsningsnummer är känt för att vara mindre än 165, se Wolfram MathWorld.
Konstruktion
Tutte 12-buren är en kubisk Hamiltonsk graf och kan definieras av LCF-notationen [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57 , 11, –21, –57, 59, –17] 7 .
Det finns, upp till isomorfism, exakt två generaliserade hexagoner av ordning (2,2) som bevisats av Cohen och Tits. De är den delade Cayley-hexagonen H(2) och dess dubbla punktlinje. Uppenbarligen har båda samma incidensgraf, vilket faktiskt är isomorft till Tutte 12-buren.
Balaban 11-buren kan konstrueras genom excision från Tutte 12-buren genom att ta bort ett litet underträd och undertrycka de resulterande hörnen av grad två.
Algebraiska egenskaper
Automorfismgruppen i Tutte 12-buren är av storleksordningen 12 096 och är en halvdirekt produkt av den projektiva speciella enhetsgruppen PSU(3,3) med den cykliska gruppen Z / 2Z . Den verkar transitivt på sina kanter men inte på sina hörn, vilket gör den till en semisymmetrisk graf , en vanlig graf som är kanttransitiv men inte vertextransitiv . Faktum är att automorfismgruppen i Tutte 12-buren bevarar de tvådelade delarna och verkar primitivt på varje del. Sådana grafer kallas bi-primitiva grafer och endast fem kubiska bi-primitiva grafer existerar; de heter Iofinova-Ivanov-graferna och är av ordningen 110, 126, 182, 506 och 990.
Alla de kubiska semisymmetriska graferna på upp till 768 hörn är kända. Enligt Conder , Malnič, Marušič och Potočnik är Tutte 12-buren den unika kubiska semisymmetriska grafen på 126 hörn och är den femte minsta möjliga kubiska semisymmetriska grafen efter Gray-grafen, Iofinova–Ivanov- vertikalgrafen på 110 , Ljubljana-grafen och en graf på 120 hörn med omkrets 8.
Det karakteristiska polynomet för Tutte 12-buren är
Det är den enda grafen med detta karakteristiska polynom; därför bestäms 12-buren av dess spektrum .
Galleri
Det kromatiska numret på Tutte 12-buren är 2.
Det kromatiska indexet för Tutte 12-buren är 3.
