Tutte 12-klec - Tutte 12-cage
| Tutte 12-klec | |
|---|---|
 Klec Tutte 12 | |
| Pojmenoval podle | W. T. Tutte |
| Vrcholy | 126 |
| Hrany | 189 |
| Poloměr | 6 |
| Průměr | 6 |
| Obvod | 12 |
| Automorfismy | 12096 |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Vlastnosti | Krychlový Klec Hamiltonian Polosymetrické Bipartitní |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Tutte 12-klec nebo Bensonův graf[1] je 3-běžný graf se 126 vrcholy a 189 hranami pojmenovanými podle W. T. Tutte.[2]
Tutte 12-klec je jedinečný (3-12) -klec (sekvence A052453 v OEIS ). Objevil jej C. T. Benson v roce 1966.[3] Má to chromatické číslo 2 (bipartitní ), chromatický index 3, obvod 12 (jako 12 klec) a průměr 6. Jeho číslo křížení je 170 a byl předpokládán jako nejmenší kubický graf s tímto číslem křížení.[4][5]
Konstrukce
Klec Tutte 12 je krychlový Hamiltonovský graf a lze je definovat pomocí LCF notace [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17]7.[6]
Existují až izomorfismus, přesně dva zobecněné šestiúhelníky řádu (2,2) jak dokazují Cohen a Tits. Jsou to dělený šestiúhelník Cayley H (2) a jeho dvojice point-line. Je zřejmé, že oba mají stejný graf výskytu, který je ve skutečnosti izomorfní s klecí Tutte 12.[1]
The Klec Balaban 11 lze sestrojit excizí z klece Tutte 12 odstraněním malého podstromu a potlačením výsledných vrcholů stupně dva.[7]
Algebraické vlastnosti
Automorfická skupina klece Tutte 12 je řádu 12 096 a je a polopřímý produkt z projektivní speciální jednotná skupina PSU (3,3) s cyklická skupina Z/2Z.[1] Působí přechodně na své hrany, ale ne na své vrcholy, což z ní činí polosymetrický graf, běžný graf, který je hrana tranzitivní ale ne vrchol-tranzitivní. Ve skutečnosti skupina automorfismu klece Tutte 12 zachovává bipartitní části a na každou část působí primitivně. Takové grafy se nazývají bi-primitivní grafy a existuje pouze pět kubických bi-primitivních grafů; jmenují se grafy Iofinova-Ivanov a jsou řádu 110, 126, 182, 506 a 990.[8]
Jsou známy všechny kubické polosymetrické grafy až na 768 vrcholech. Podle Conder, Malnič, Marušič a Potočnik, klec Tutte 12 je jedinečný kubický polosymetrický graf na 126 vrcholech a je pátým nejmenším možným kubickým polosymetrickým grafem po Šedý graf, Iofinova – Ivanovův graf na 110 vrcholech, Lublaňský graf a graf na 120 vrcholech s obvodem 8.[9]
The charakteristický polynom klece Tutte 12 je
Je to jediný graf s tímto charakteristickým polynomem; proto je klec 12 určena jeho spektrum.
Galerie
The chromatické číslo klece Tutte 12 je 2.
The chromatický index klece Tutte 12 je 3.
Reference
- ^ A b C Geoffrey Exoo a Robert Jajcay, průzkum dynamické klece, Electr. J. Combin. 15 (2008).
- ^ Weisstein, Eric W. "Tutte 12-klec". MathWorld.
- ^ Benson, C. T. „Minimální pravidelné grafy obvodu 8 a 12.“ Umět. J. Math. 18, 1091–1094, 1966.
- ^ Exoo, G. "Přímočaré kresby slavných grafů".
- ^ Pegg, E. T. a Exoo, G. „Crossing Number Graphs.“ Mathematica J. 11, 2009.
- ^ Polster, B. Geometrická obrázková kniha. New York: Springer, str. 179, 1998.
- ^ Balaban, A. T. „Trivalentní grafy obvodu devíti a jedenácti a vztahů mezi klecemi.“ Rev. Roumaine Math 18, 1033–1043, 1973.
- ^ Iofinova, M. E. a Ivanov, A. A. „Bi-primitivní kubické grafy.“ In Investigations in the Algebraic Theory of Combinatorial Objects. 123–134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moskva, str. 137–152, 1985.)
- ^ Conder, Marstone; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), „Sčítání polosymetrických kubických grafů až na 768 vrcholech“, Journal of Algebraic Combinatorics, 23: 255–294, doi:10.1007 / s10801-006-7397-3.