Tatta cu 12 celule

Graficul lui Tutt cu 12 celule ( Benson graph [1] ) este un graf regulat de 3 cu 126 de vârfuri și 189 de muchii, numit după William Tutt [2] .

Este singura (3-12)- celula [3] ; are un număr cromatic de 2 ( bipartit ), un indice cromatic de 3, o circumferință de 12 (ca 12 celule) și un diametru de 6; numărul de intersecții este 170 și se presupune că acest grafic este minim cu numărul dat de intersecții [4] [5] .

Descoperit de Clark Benson în 1966 [6] .

Clădire

Celula Tutt cu 12 celule este un grafic hamiltonian cubic și poate fi definit prin codul LCF [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57 , 11, −21, −57, 59, −17] 7 [7] .

După cum au demonstrat Cohen și Tits, există, până la izomorfism, exact două hexagoane generalizate de ordinul (2,2) . Acestea sunt hexagonul Cayley rupt H(2) și dualul său (prin puncte/linii). Este clar că ambele au același grafic de incidență, care este, de fapt, izomorf cu 12 celule a lui Tutt [1] .

Celula Balaban cu 11 poate fi construită prin tăierea unui mic subarbore din celula Tutt cu 12 și ștergerea vârfurilor rezultate de gradul doi [8] .

Proprietăți algebrice

Automorfismul de grup al celulei Tutt 12 are ordinul 12096 și este un produs semidirect al grupului unitar proiectiv special PSU(3,3) cu grupul ciclic Z /2 Z [1] . Grupul acționează tranzitiv pe muchii, dar nu pe vârfuri, făcându-l un graf semisimetric , un graf obișnuit care este tranzitiv la muchie , dar nu tranzitiv la vârf . De fapt, automorfismul grupului de 12 celule Tutt păstrează părțile graficului și acționează pur și simplu asupra fiecăreia dintre ele. Astfel de grafice sunt numite biprimitive și există doar cinci grafice biprimitive cubice. Se numesc grafice Ivanov-Iofinova și au ordinele 110, 126, 182, 506 și 990 [9] .

Sunt cunoscute toate graficele cubice semisimetrice care conțin până la 768 de vârfuri. Potrivit lui Konder, Malnic, Marusic și Potočnik, Tutta cu 12 celule este singurul grafic semisimetric cu 126 de vârfuri și al cincilea cel mai mic grafic semisimetric cubic posibil după graficul Gray , graficul Ivanov-Iofinova cu 110 vârfuri , graficul Ljubljana , iar graficul cu 120 de vârfuri cu circumferința 8 [10 ] .

Polinomul caracteristic al Tatta cu 12 celule este egal cu

Graficul este singurul cu acest polinom caracteristic, astfel încât celula de 12 este definită de spectrul său .

Galerie

• Numărul cromatic al Tatta cu 12 celule este 2.

• Indicele cromatic al Tatta cu 12 celule este 3.

Note

1. ↑ 1 2 3 Exoo, Jajcay, 2008 .
2. ^ Weisstein , Eric W. Tutte 12-cage  pe site- ul Wolfram MathWorld .
3. ↑ Secvența OEIS A052453 _
4. ↑ Exoo, 2006 .
5. ↑ Pegg, Exoo, 2009 .
6. ↑ Benson, 1966 , p. 1091-1094.
7. ↑ Polster, 1998 , p. 179.
8. ↑ Balaban, 1973 , p. 1033-1043.
9. ↑ Ivanov, Iofinova, 1985 , p. 123-134.
10. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , p. 255–294.

Literatură

• Benson CT Grafice regulate minime ale circumferinței 8 și 12 // Can. J. Math .. - 1966. - Ediţia. 18 .
• Exoo G. Desene rectilinii ale graficelor celebre . — 2006.
• Pegg ET, Exoo G. Crossing Number Graphs // Mathematica J.. - 2009. - Vol. 11 .
• Cartea cu imagini geometrice Polster BA . - New York: Springer Science + Business Media, LLC, 1998. - (Universitex). — ISBN 978-1-4612-6426-2 . - ISBN 978-1-4619-8526-2 .
• Balaban AT Grafice trivalente ale circumferinței nouă și unsprezece și relații între cuști // Rev. Roumaine Math. - 1973. - Emisiune. 18 .
• Geoffrey Exoo, Robert Jajcay. Studiu dinamic în cușcă // Electr. J. Combin. - 2008. - Emisiune. 15 .
• Ivanov A. A., Iofinova M. E. Grafice cubice biprimitive // ​​Studii în teoria algebrică a obiectelor combinatorii. - M. , 1985. - S. 137-152. - (Seria: Institutul de Cercetare All-Russian pentru Cercetarea Sistemelor. Lucrările seminarului).
• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. Un recensământ de grafice cubice semisimetrice pe până la 768 de vârfuri // Journal of Algebraic Combinatorics. - 2006. - T. 23 . — S. 255–294 . - doi : 10.1007/s10801-006-7397-3 .