Greve af Srikhande

Greve af Srikhande

Opkaldt efter	S. S. Srikhande
Toppe	16
ribben	48
Radius	2
Diameter	2
Omkreds	3
Automorfismer	192
Kromatisk tal	fire
Kromatisk indeks	6
Ejendomme	Stærkt regulært Hamiltonsymmetrisk Euler - heltal
bogtykkelse	fire
Antal køer	3
Mediefiler på Wikimedia Commons

Jarlen af Shrikhande er en greve fundet af S.S. Shrikhande ( engelsk ) i 1959 [1] [2] . Grafen er meget regelmæssig , har 16 spidser og 48 kanter , og hvert spidspunkt har grad 6. Hvert knudepar har præcis to fælles naboer, uanset om parret er forbundet med en kant.

Konstruktion

Shrikhande-grafen kan konstrueres som en Cayley-graf , hvori sættet af knudepunkter er , og to knudepunkter er forbundet, hvis og kun hvis forskellen er i . ${\displaystyle \mathbb {Z} _{4}\times \mathbb {Z} _{4))$ ${\displaystyle \{\pm (1,0),\pm (0,1),\pm (1,1)\))$

Egenskaber

I Shrikhand-grafen har alle to hjørner I og J to forskellige fælles naboer (undtagen selve hjørnerne I og J ), hvilket er sandt, uanset om I og J er tilstødende eller ej. Med andre ord er grafen meget regelmæssig , og dens parametre er: {16,6,2,2}, dvs. Det følger af denne lighed, at grafen er forbundet med symmetriske balancerede ufuldstændige blokdesigns ( eng. Balanced Incomplete Block Designs , BIBD). Shrikhande-grafen deler disse parametre med nøjagtig én anden graf, 4×4 - tårn-grafen , det vil sige linjegrafen L ( K 4,4 ) af den komplette todelte graf K 4,4 . Den sidste graf er den eneste linjegraf L ( K n, n ), for hvilken de stærke regularitetsparametre ikke entydigt definerer denne graf, og grafen deler dem med en anden graf, nemlig Shrikhande-grafen (som ikke er en tårngraf) [ 2] [3] . $\lambda =\mu =2$

Grafen for Srikhande er lokalt sekskantet . Det vil sige, at naboerne til hvert toppunkt danner en cyklus på seks toppunkter. Som enhver lokalt cyklisk graf er Shrikhande-grafen 1-skelettet Whitney-trianguleringen af en overflade. I tilfældet med Shrikhande-grafen er denne overflade en torus , hvor hvert toppunkt er omgivet af seks trekanter [4] Således er Shrikhande-grafen en toroidal graf . Indlejringen danner en regelmæssig afbildning til en torus med 32 trekantede flader. Skelettet af den dobbelte graf af denne kortlægning (som indlejret i en torus) er Dyck-grafen , en kubisk symmetrisk graf.

Shrikhande -grafen er ikke afstandstransitiv . Dette er den mindste afstand-regulære graf , der ikke er afstandstransitiv [5] .

Automorfigruppen i Shrikhande-grafen har orden 192. Den virker transitivt på grafens toppunkter, kanter og buer. Derfor er Shrikhande-grafen en symmetrisk graf .

Det karakteristiske polynomium for Shrikhande-grafen er . Shrikhande-grafen er således en hel graf - dens spektrum består udelukkende af heltal. $(x-6)(x-2)^{6}(x+2)^{9}$

Grafen har bogtykkelse 4 og antal køer 3 [6] .

Galleri

Grafen for Srikhande er ringformet .
Grev Srikhandes kromatiske tal er 4.
Grev Shrikhandes kromatiske indeks er 6.
Greven af Srikhande, tegnet symmetrisk.
Grev Srikhande af Hamiltons .

Noter

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

Litteratur

Shrikhande SS Det unikke ved L 2 - foreningsordningen // 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. Engineering Lineære Layouts med SAT. - Universitetet i Tübingen, 2018. - (Kandidatspeciale).