Srikhanden kreivi
| Srikhanden kreivi | |
|---|---|
| Nimetty | S. S. Srikhande |
| Huiput | 16 |
| kylkiluut | 48 |
| Säde | 2 |
| Halkaisija | 2 |
| Ympärysmitta | 3 |
| Automorfismit | 192 |
| Kromaattinen numero | neljä |
| Kromaattinen indeksi | 6 |
| Ominaisuudet |
Voimakkaasti säännöllinen Hamiltonin symmetrinen Euler -kokonaisluku |
| kirjan paksuus | neljä |
| Jonojen määrä | 3 |
| Mediatiedostot Wikimedia Commonsissa | |
Earl of Shrikhande on kreivi , jonka S.S. Shrikhande ( englanti ) löysi vuonna 1959 [1] [2] . Graafi on vahvasti säännöllinen , siinä on 16 kärkeä ja 48 reunaa ja jokaisella kärjellä on aste 6. Jokaisella solmuparilla on täsmälleen kaksi yhteistä naapuria riippumatta siitä, onko pari yhdistetty reunalla vai ei.
Rakentaminen
Shrikhande-graafi voidaan rakentaa Cayley-graafina , jossa kärkijoukko on , ja kaksi kärkeä on yhdistetty silloin ja vain, jos ero on .
Ominaisuudet
Shrikhand-graafissa millä tahansa kahdella kärjellä I ja J on kaksi erilaista yhteistä naapuria (pois lukien itse pisteet I ja J ), mikä on totta riippumatta siitä, ovatko I ja J vierekkäisiä vai eivät. Toisin sanoen graafi on vahvasti säännöllinen ja sen parametrit ovat: {16,6,2,2}, eli . Tästä yhtälöstä seuraa, että kuvaaja liittyy symmetrisiin tasapainotettuihin epätäydellisiin lohkosuunnitelmiin ( eng. Balanced Incomplete Block Designs , BIBD). Shrikhande-graafi jakaa nämä parametrit täsmälleen yhden muun graafin, 4×4- pylvään graafin kanssa , eli täydellisen kaksiosaisen graafin K 4,4 viivagraafin L ( K 4,4 ) . Viimeinen graafi on ainoa viivagraafi L ( K n, n ), jonka vahvat säännöllisyysparametrit eivät määrittele yksiselitteisesti tätä graafia, ja graafi jakaa ne toisen graafin kanssa, nimittäin Shrikhande-graafin (joka ei ole tornigraafi) kanssa [ 2] [3] .
Srikhanden kuvaaja on paikallisesti kuusikulmainen . Toisin sanoen kunkin kärjen naapurit muodostavat kuuden kärjen syklin . Kuten mikä tahansa paikallisesti syklinen graafi, Shrikhande-graafi on jonkin pinnan Whitney -kolmioiden 1-luuranko Shrikhande-graafin tapauksessa tämä pinta on torus , jossa jokaista kärkeä ympäröi kuusi kolmiota [4] Siten Shrikhande-graafi on toroidinen graafi . Upotus muodostaa säännöllisen kartoituksen torukseksi, jossa on 32 kolmiopintaa. Tämän kartoituksen kaksoisgraafin luuranko (torukseen upotettuna) on Dyck-graafi , kuutiosymmetrinen graafi.
Shrikhande -kaavio ei ole etäisyystransitiivinen . Tämä on pienin etäisyys-säännöllinen kuvaaja , joka ei ole etäisyystransitiivinen [5] .
Shrikhande-graafin automorfismiryhmän järjestys on 192. Se vaikuttaa transitiivisesti graafin kärkipisteisiin, reunoihin ja kaareihin. Siksi Shrikhande-graafi on symmetrinen graafi .
Shrikhande-graafin ominaispolynomi on . Siten Shrikhande-graafi on kokonainen graafi - sen spektri koostuu kokonaan kokonaisluvuista.
Graafilla on kirjan paksuus 4 ja jonoja 3 [6] .
Galleria
-
Srikhanden kaavio on toroidinen .
-
Srikhanden kreivi, piirretty symmetrisesti.
-
Hamiltonien kreivi Srikhande .
Muistiinpanot
- ↑ Weisstein , Eric W. Shrikhande Graph Wolfram MathWorld -verkkosivustolla .
- ↑ 1 2 Shrikhande, 1959 , s. 781–798.
- ↑ Harary, 1972 , s. 79.
- ↑ Brouwer AE Shrikhande graph Arkistoitu 9. maaliskuuta 2014 Wayback Machineen .
- ↑ Brouwer, Cohen, Neumaier 1989 , s. 104–105, 136.
- ↑ Volz, 2018 .
Kirjallisuus
- Shrikhande SS L 2 -assosiaatiojärjestelmän ainutlaatuisuus // Annals of Mathematical Statistics. - 1959. - T. 30 . — S. 781–798 . - doi : 10.1214/aoms/1177706207 . — .
- Frank Harary. graafiteoria . - Massachusetts: Addison-Wesley, 1972.
- Harari F. Graafiteoria. - M . : "Mir", 1973.
- , ISBN 0-521-43594-3
- Brouwer AE, Cohen AM, Neumaier A. Etäisyyssäännölliset kaaviot. - New York: Springer-Verlag, 1989. - S. 104-105, 136.
- Jessica Walz. Lineaaristen asettelujen suunnittelu SAT:n avulla. - Tübingenin yliopisto, 2018. - (Pro gradu).
Linkit
- The Shrikhande Graph arkistoitu 24. marraskuuta 2010, Wayback Machine , Peter Cameron, elokuu 2010.