12-soluinen Tatta

Tuttin 12-soluinen ( Benson-graafi [1] ) on 3 - säännöllinen graafi , jossa on 126 kärkeä ja 189 reunaa ja joka on nimetty William Tuttin mukaan [2] .

Onko ainoa (3-12)- solu [3] ; sen kromaattinen luku on 2 ( kaksiosainen ), kromaattinen indeksi 3, ympärysmitta 12 (12-soluisena) ja halkaisija 6; leikkauspisteiden määrä on 170 ja oletetaan, että tämä kuvaaja on minimaalinen annetulla leikkauspisteiden määrällä [4] [5] .

Clark Benson löysi sen vuonna 1966 [6] .

Rakentaminen

Tutt 12-solu on kuutio Hamiltonin graafi, ja se voidaan määritellä LCF-koodilla [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57 , 11, −21, −57, 59, −17] 7 [7] .

Kuten Cohen ja Tits osoittivat, isomorfismiin asti on olemassa täsmälleen kaksi yleistettyä kuusikulmiota järjestyksessä (2,2) . Nämä ovat katkonainen Cayleyn kuusikulmio H(2) ja sen kaksois (pisteillä/viivoilla). On selvää, että molemmilla on sama esiintyvyyskäyrä, joka on itse asiassa isomorfinen Tuttin 12-soluiselle [1] .

Balaban 11 -solu voidaan rakentaa leikkaamalla pieni alipuu Tutt 12 -solusta ja poistamalla tuloksena saadut asteen kaksi kärkipisteet [8] .

Algebralliset ominaisuudet

Tutt 12-solun ryhmäautomorfismi on luokkaa 12096 ja se on puolisuora tulo projektiivisestä erityisestä unitaariryhmästä PSU(3,3) syklisen ryhmän Z /2 Z [1] kanssa . Ryhmä toimii transitiivisesti reunoissa, mutta ei pisteissä, mikä tekee siitä puolisymmetrisen graafin , säännöllisen graafin, joka on reunatransitiivinen , mutta ei kärkitransitiivinen . Itse asiassa Tutt 12-soluryhmän automorfismi säilyttää graafin osat ja vaikuttaa yksinkertaisesti jokaiseen niistä. Tällaisia ​​kaavioita kutsutaan biprimitiivisiksi ja niitä on vain viisi kuutiometriä biprimitiivistä kuvaajaa. Niitä kutsutaan Ivanov-Iofinova-graafiksi ja niillä on järjestys 110, 126, 182, 506 ja 990 [9] .

Kaikki kuutioiset puolisymmetriset graafit, jotka sisältävät jopa 768 kärkeä, tunnetaan. Konderin, Malnicin, Marusicin ja Potočnikin mukaan 12-soluinen Tutta on ainoa 126-pisteinen puolisymmetrinen graafi ja viidenneksi pienin mahdollinen kuutioinen puolisymmetrinen graafi Grayn graafin , 110-pisteisen Ivanov-Iofinova- graafin , Ljubljana - graafin jälkeen, ja 120 kärjen graafi, jonka ympärysmitta on 8 [10 ] .

12-soluisen Tattan ominaispolynomi on yhtä suuri kuin

Graafi on ainoa, jolla on tämä ominaispolynomi, joten 12-solun määrittää sen spektri .

Galleria

• 12-soluisen Tattan kromaattinen luku on 2.

• 12-soluisen Tattan kromaattinen indeksi on 3.

Muistiinpanot

1. ↑ 1 2 3 Exoo, Jajcay, 2008 .
2. ↑ Weisstein, Eric W. Tutte 12-häkki  Wolfram MathWorld -verkkosivustolla .
3. ↑ OEIS - sekvenssi A052453 _
4. ↑ Exoo, 2006 .
5. ↑ Pegg, Exoo, 2009 .
6. ↑ Benson, 1966 , s. 1091-1094.
7. ↑ Polster, 1998 , s. 179.
8. ↑ Balaban, 1973 , s. 1033-1043.
9. ↑ Ivanov, Iofinova, 1985 , s. 123-134.
10. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , s. 255–294.

Kirjallisuus

• Benson CT Minimal Regular Graphs of Girth 8 and 12 // Can. J. Math .. - 1966. - Numero. 18 .
• Exoo G. Suoraviivaiset piirrokset kuuluisista kaavioista . – 2006.
• Pegg ET, Exoo G. Crossing Number Graphs // Mathematica J.. - 2009. - Voi. 11 .
• Polster BA Geometrinen kuvakirja. - New York: Springer Science + Business Media, LLC, 1998. - (Universitex). — ISBN 978-1-4612-6426-2 . - ISBN 978-1-4619-8526-2 .
• Balaban AT Trivalent Graphs of Girth Nine and Eleven and Relationships among the Cages // Rev. Roumaine Math. - 1973. - Numero. 18 .
• Geoffrey Exoo, Robert Jajcay. Dynaaminen häkkitutkimus // Electr. J. Combin. - 2008. - Ongelma. 15 .
• Ivanov A. A., Iofinova M. E. Biprimitiiviset kuutiograafit // Kombinatoristen objektien algebrallisen teorian tutkimukset. - M. , 1985. - S. 137-152. - (Sarja: All-Russian Research Institute for System Research. Proceedings of the Seminar).
• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. Puolisymmetristen kuutiograafien laskenta jopa 768 kärkeen // Journal of Algebraic Combinatorics. - 2006. - T. 23 . — S. 255–294 . - doi : 10.1007/s10801-006-7397-3 .