Greve av Srikhande

Greve av Srikhande

Döpt efter	S. S. Srikhande
Toppar	16
revben	48
Radie	2
Diameter	2
Omkrets	3
Automorfismer	192
Kromatiskt nummer	fyra
Kromatiskt index	6
Egenskaper	Starkt regelbundet Hamiltonian Symmetric Euler Integer
boktjocklek	fyra
Antal köer	3
Mediafiler på Wikimedia Commons

The Earl of Shrikhande är en greve som hittades av S.S. Shrikhande ( engelska ) 1959 [1] [2] . Grafen är starkt regelbunden , har 16 hörn och 48 kanter , och varje hörn har grad 6. Varje nodpar har exakt två gemensamma grannar, oavsett om paret är sammankopplat med en kant eller inte.

Byggnad

Shrikhande-grafen kan konstrueras som en Cayley-graf där uppsättningen av hörn är , och två hörn är sammankopplade om och endast om skillnaden är i . ${\displaystyle \mathbb {Z} _{4}\times \mathbb {Z} _{4))$ ${\displaystyle \{\pm (1,0),\pm (0,1),\pm (1,1)\))$

Egenskaper

I Shrikhand-grafen har alla två hörn I och J två olika gemensamma grannar (exklusive själva hörnen I och J ), vilket är sant oavsett om I och J är intilliggande eller inte. Med andra ord är grafen starkt regelbunden och dess parametrar är: {16,6,2,2}, dvs. Det följer av denna likhet att grafen är associerad med symmetriska balanserade ofullständiga blockdesigner ( eng. Balanced Incomplete Block Designs , BIBD). Shrikhande-grafen delar dessa parametrar med exakt en annan graf, 4×4 torngrafen , det vill säga linjegrafen L ( K 4,4 ) för den kompletta tvådelade grafen K 4,4 . Den sista grafen är den enda linjegrafen L ( K n, n ) för vilken de starka regularitetsparametrarna inte unikt definierar denna graf, och grafen delar dem med en annan graf, nämligen Shrikhande-grafen (som inte är en torngraf) [ 2] [3] . $\lambda =\mu =2$

Grafen för Srikhande är lokalt hexagonal . Det vill säga, grannarna till varje hörn bildar en cykel av sex hörn. Liksom alla lokalt cykliska grafer är Shrikhande-grafen 1-skelettet Whitney-trianguleringen av någon yta. I fallet med Shrikhande-grafen är denna yta en torus , där varje vertex omges av sex trianglar [4] Således är Shrikhande-grafen en toroidal graf . Inbäddningen bildar en regelbunden mappning till en torus med 32 triangulära ytor. Skelettet av den dubbla grafen för denna mappning (som inbäddad i en torus) är Dyck-grafen , en kubisk symmetrisk graf.

Shrikhande -grafen är inte distanstransitiv . Detta är den minsta avstånds-reguljära grafen som inte är avståndstransitiv [5] .

Automorfismgruppen i Shrikhande-grafen har ordning 192. Den verkar transitivt på grafens hörn, kanter och bågar. Därför är Shrikhande-grafen en symmetrisk graf .

Det karakteristiska polynomet för Shrikhande-grafen är . Således är Shrikhande-grafen en hel graf - dess spektrum består helt av heltal. ${\displaystyle (x-6)(x-2)^{6}(x+2)^{9))$

Grafen har boktjocklek 4 och antal köer 3 [6] .

Galleri

Grafen för Srikhande är toroidformad .
Greve Srikhandes kromatiska nummer är 4.
Greve Shrikhandes kromatiska index är 6.
Greven av Srikhande, ritad symmetriskt.
Greve Srikhande av Hamiltons .

Anteckningar

↑ Weisstein, Eric W. Shrikhande Graph på Wolfram MathWorld- webbplatsen .
↑ 1 2 Shrikhande, 1959 , sid. 781–798.
↑ Harary, 1972 , sid. 79.
↑ Brouwer AE Shrikhande graf Arkiverad 9 mars 2014 på Wayback Machine .
↑ Brouwer, Cohen, Neumaier 1989 , sid. 104–105, 136.
↑ Volz, 2018 .

Litteratur

Shrikhande SS Det unika med L 2 associationsschemat // Annals of Mathematical Statistics. - 1959. - T. 30 . — S. 781–798 . - doi : 10.1214/aoms/1177706207 . — .
Frank Harary. grafteori . — Massachusetts: Addison-Wesley, 1972.
- Harari F. Grafteori. - M . : "Mir", 1973.
, ISBN 0-521-43594-3
Brouwer AE, Cohen AM, Neumaier A. Distance-Regular Graphs. - New York: Springer-Verlag, 1989. - S. 104-105, 136.
Jessica Walz. Tekniska linjära layouter med SAT. - Universitetet i Tübingen, 2018. - (Masteruppsats).

Länkar

Shrikhande-grafen arkiverad 24 november 2010 på Wayback Machine , Peter Cameron, augusti 2010.