Tutte 12-klatka
| Tutte 12-klatka | |
|---|---|
 Tutte 12-klatka
| |
| Nazwany po | WT Tutte |
| Wierzchołki | 126 |
| Krawędzie | 189 |
| Promień | 6 |
| Średnica | 6 |
| Obwód | 12 |
| Automorfizmy | 12096 |
| Liczba chromatyczna | 2 |
| Indeks chromatyczny | 3 |
| Nieruchomości |
Półsymetryczna dwudzielna klatka sześcienna hamiltonianu |
| Tabela wykresów i parametrów | |
W matematycznej dziedzinie teorii grafów graf Tutte 12-cage lub Benson jest 3- regularnym grafem ze 126 wierzchołkami i 189 krawędziami, nazwanymi na cześć WT Tutte .
Klatka Tutte 12 jest unikalną klatką (3-12) (sekwencja A052453 w OEIS ). Został odkryty przez CT Bensona w 1966 roku. Ma liczbę chromatyczną 2 ( dwudzielna ), indeks chromatyczny 3, obwód 12 (jako klatka 12) i średnicę 6. Wiadomo, że jego liczba skrzyżowań jest mniejsza niż 165, patrz Wolfram MathWorld .
Budowa
12-klatka Tutte jest sześciennym grafem Hamiltona i może być zdefiniowana za pomocą notacji LCF [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57 , 11, –21, –57, 59, –17] 7 .
Istnieją, z dokładnością do izomorfizmu, dokładnie dwa uogólnione sześciokąty rzędu (2,2) , jak udowodnili Cohen i Tits. Są to podzielony sześciokąt Cayleya H (2) i jego podwójna linia punktowa. Najwyraźniej oba z nich mają ten sam wykres występowania, który w rzeczywistości jest izomorficzny z 12-klatką Tutte.
Klatkę Balaban 11 można skonstruować przez wycięcie z klatki Tutte 12 poprzez usunięcie małego poddrzewa i wyeliminowanie powstałych wierzchołków stopnia drugiego.
Właściwości algebraiczne
Grupa automorfizmów klatki Tutte 12 jest rzędu 12 096 i jest półprostym iloczynem rzutowej specjalnej grupy unitarnej PSU(3,3) z grupą cykliczną Z / 2Z . Działa przechodnie na swoich krawędziach, ale nie na wierzchołkach, co czyni go grafem półsymetrycznym , regularnym grafem, który jest przechodni przez krawędzie , ale nie przechodni przez wierzchołki . W rzeczywistości grupa automorfizmów 12-klatkowej Tutte zachowuje dwudzielne części i działa prymitywnie na każdą część. Takie grafy nazywane są grafami bi-prymitywnymi i istnieje tylko pięć sześciennych grafów bi-prymitywnych; noszą one nazwę wykresów Iofinova-Ivanov i są rzędu 110, 126, 182, 506 i 990.
Znane są wszystkie sześcienne grafy półsymetryczne na maksymalnie 768 wierzchołkach. Według Condera , Malniča, Marušiča i Potočnika, 12-klatkowa klatka Tutte jest unikalnym sześciennym grafem półsymetrycznym na 126 wierzchołkach i jest piątym możliwym najmniejszym grafem półsymetrycznym sześciennym po wykresie Graya, grafie Iofinova – Ivanov na 110 wierzchołkach , graf Lublany i graf na 120 wierzchołkach o obwodzie 8.
Charakterystyczny wielomian klatki Tutte 12 to
Jest to jedyny wykres z tym charakterystycznym wielomianem; dlatego klatka 12 jest określona przez jej widmo .
Galeria
Liczba chromatyczna klatki Tutte 12 wynosi 2.
Indeks chromatyczny klatki Tutte 12 wynosi 3.
