Earl of Dejter

Dejter-graafi on 6-säännöllinen graafi, jossa on 112 kärkeä, 336 reunaa ja ympärysmitta 4 [1] [2] [3] [4] [5] [6] [7] . Dejter-graafi saadaan poistamalla kopio Hamming-koodista, jonka pituus on 7, binäärisestä 7- kuutiosta .

Kuvaus

Dejter-graafi ja mikä tahansa graafi, joka on saatu poistamalla Hamming-koodi, jonka pituus on 2 r -1 (2 r -1) -kuutiosta , on symmetrinen graafi (ja siksi kärkitransitiivinen ja reunatransitiivinen , mutta ei puolitransitiivinen ). Erityisesti Dejterin graafi sallii 3 - hajottamisen kahdeksi kopioksi Ljubljanan graafista , joka on kolmanneksi pienin reunatransitiivinen graafi, mutta ei säännöllisen asteen 3 huipputransitiivinen graafi. Tällaisia ​​graafia kutsutaan puolisymmetrisiksi kuutiograafiksi .

Itse asiassa on todistettu, että Dejter-graafi voi olla 2-värinen, esimerkiksi käyttämällä joukkoa {punainen, sininen}, kuten oikealla olevassa yläkuvassa, niin että molemmat samanvärisistä reunoista koostuvat graafit ovat kopioita Ljubljanan kaavio . Näissä kahdessa kopiossa on täsmälleen 112 Dejter-graafin kärkeä ja kummassakin 168 reunaa, molemmilla kopioilla on ympärysmitta 10, kun taas Dejter-graafin ympärysmitta on 6 ja 7-kuution ympärysmitta 4. Dejter-graafi on ilmeisesti pienin symmetrinen graafi , jolla on yhdistetty itsekomplementaarinen huippupisteen kiristys puolisymmetrinen kuutioosagraafi.

Sekä punainen että sininen Ljubljanan aligraafit, jotka yhdistävät Dejter-graafin kärjet, voidaan esittää Heawood - graafin peittograafina , nimittäin Heawood-graafin 8- kaneina . Tämä voidaan saada molemmissa Ljubljana-graafin esityksissä (punainen ylhäällä, sininen alla, molemmat oikealla) värjäämällä vuorotellen Heawood-graafin peräkkäiset kärjet , esimerkiksi mustaksi ja valkoiseksi (näkee paremmin kaksoisnapsauttamalla). kuvassa suuremmaksi), koska Heawood-graafin kaksiosainen . Jokainen tällainen kuva muodostuu 8 naapurista 7-kuution kiinteää koordinaattia pitkin, jolloin puolella Hamming-koodista on kiinteät painot 0 tai 1. Vaihtamalla nämä painot permutoimalla (0 1) voidaan siirtyä määritetystä viereisyydestä. punaisella Ljubljana-graafilla sinisen Ljubljana-graafin määrittelemään viereisyyteen ja päinvastoin.

Dejter-graafin seitsemäs osa on esitetty erillisessä kuvassa alla, ja se voidaan saada kahdesta tuloksena olevasta Heawood-graafin kopiosta .

Muistiinpanot

1. ↑ Klin, Lauri, Ziv-Av, 2012 , s. 1175–1191.
2. ↑ Borges, Dejter, 1996 , s. 161-173.
3. ↑ Dejter, 1994 , s. 55–66.
4. ↑ Dejter, 1997 , s. 301–309.
5. ↑ Dejter, Guan, 1989 , s. 162-174.
6. ↑ Dejter, Pujol, 1995 , s. 18-32.
7. ↑ Dejter, Weichsel, 1993 , s. 67–78.

Kirjallisuus

• Klin M., Lauri J., Ziv-Av M. Linkit kahden puolisymmetrisen graafin välillä 112 kärjessä assosiaatiokaavioiden linssin kautta // Jour. Symbolic Comput.. - 2012. - V. 47 , no. 10 .
• Borges J., Dejter IJ Täydellisistä hallitsevista sarjoista hyperkuutioissa ja niiden komplementeissa // J. Combin. Matematiikka. Yhdistää. Comput.. - 1996. - Numero. 20 .
• Dejter IJ 7-kuution symmetrisistä osagraafista: yleiskatsaus // Discrete Math.. - 1994. - Vol. 124 .
• Dejter IJ 7-kuution Hamming-kuoren tekijöiden symmetria // J. Combin. Des.. - 1997. - Numero. 5 .
• Dejter IJ, Guan P. Neliön estoreunojen osajoukot hyperkuutioissa ja huippupisteiden välttämisessä // Graafiteoria, kombinatoriikka, algoritmit ja sovellukset, SIAM. - San Francisco, Kalifornia, 1989.
• Dejter IJ, Pujol J. Täydellinen ylivalta ja symmetria hyperkuutioissa // Proceedings of the Twenty-6th Southeastern International Conference on Combinatorics, Graph Theory and Computing. - Boca Raton, Florida, 1995. - T. 111. - (Congr. Numer.).
• Dejter IJ, Weichsel PM Twisted perfect dominating subgraphs of hypercubes // Proceedings of the Twenty-4th Southeastern International Conference on Combinatoriics, Graph Theory, and Computing (Boca Raton, Florida, 1993).. - 1993.