Ljubljanan kreivi

Ljubljanan graafi on suuntaamaton kaksiosainen graafi , jossa on 112 kärkeä ja 168 reunaa [1] .

Graafi on kuutiograafi , jonka halkaisija on 8, säde 7, kromaattinen luku 2 ja kromaattinen indeksi 3. Sen ympärysmitta on 10 ja siinä on tarkalleen 168 jaksoa, joiden pituus on 10. Lisäksi on 168 sykliä, joiden pituus on 12 [2] .

Rakentaminen

Ljubljanan graafi on Hamiltonin graafinen ja se voidaan muodostaa LCF-koodista  : [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49 , 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, - 31, -39] 2 .

Ljubljanan graafi on Ljubljanan konfiguraation Lévy-graafi, nelikulmioton konfiguraatio, jossa on 56 viivaa ja 56 pistettä [2] . Tässä kokoonpanossa jokainen suora sisältää täsmälleen 3 pistettä, jokainen piste kuuluu tasan 3 suoralle ja mitkä tahansa kaksi suoraa leikkaavat enintään yhdessä pisteessä.

Algebralliset ominaisuudet

Ljubljana-graafin automorfismiryhmä on luokkaa 168 oleva ryhmä. Se toimii transitiivisesti reunoissa, mutta ei pisteissä - on symmetrioita , jotka vievät minkä tahansa reunan mihin tahansa toiseen reunaan, mutta ei ole symmetriaa, joka vie minkä tahansa kärjen mihinkään toiseen kärkeen. . Siksi Ljubljanan graafi on puolisymmetrinen graafi , kolmas kuutioinen puolisymmetrinen graafi Grayn graafin jälkeen, jossa on 54 pistettä, ja Ivanov-Iofinovan graafin jälkeen, jossa on 110 pistettä [3] .

Ljubljanan graafin ominaispolynomi on

Historia

Brouwer, Dejter ja Thomassen [4] julkaisivat Ljubljanan kreivin ensimmäisen kerran vuonna 1993 Dejter Countin [5] itseään täydentävänä aligraafina .

Vuonna 1972 Brouwer puhui jo Fosterin löytämästä 112 kärjen reunatransitiivisesta, mutta ei kärkitransitiivisestä kuutiograafista, jota ei julkaistu [6] . Conder, Malnic, Marušić ja Potocnik löysivät uudelleen tämän 112-pisteisen graafin vuonna 2002 ja antoivat sille nimen Ljubljanan kreivi Slovenian pääkaupungin mukaan [2] . He osoittivat, että graafi oli ainoa 112 kärjen reunatransitiivinen, mutta ei huippupistetransitiivinen kuutiograafi, ja siksi se on sama graafi, jonka Foster löysi.

Galleria

• Ljubljanan graafi on Hamiltonin ja kaksiosainen.

• Ljubljanan kreivin kromaattinen indeksi on 3.

• Vaihtoehtoinen piirros Ljubljanan kreivistä.

• Ljubljanan kreivi on tämän kokoonpanon Levi-kreivi.

Muistiinpanot

1. ↑ Weisstein, Eric W. Ljubljana Graph  Wolfram MathWorld -verkkosivustolla .
2. ↑ 1 2 3 Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
3. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , s. 255-294.
4. ↑ Brouwer, Dejter, Thomassen, 1993 , s. 25-29.
5. ↑ Klin, Lauri, Ziv-Av, 2012 , s. 1175–1191.
6. ↑ Bouwer, 1972 , s. 32-40.

Kirjallisuus

• 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 .
• Brouwer AE, Dejter IJ, Thomassen C. Highly Symmetric Subgraphs of Hypercubes // J. Algebraic Combinat.. - 1993. - Voi. 2 .
• Klin M., Lauri J., Ziv-Av M. Linkit kahden puolisymmetrisen graafin välillä 112 kärjessä assosiaatiokaavioiden linssin kautta // Jour. Symbolic Comput.. - 2012. - V. 7 , no. 10 .
• Bouwer IZ reunassa, mutta ei huippupisteessä Transitiiviset säännölliset kuvaajat // J. Combin. th. Ser. B. - 1972. - Numero. 12 .
• Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph  // IMFM Preprints. - Ljubljana: Matematiikan, fysiikan ja mekaniikan instituutti, 2002. - V. 40 , no. 845 .