Contele de Srikhande

Contele de Shrikhande  este un conte găsit de S.S. Shrikhande ( în engleză ) în 1959 [1] [2] . Graficul este puternic regulat , are 16 vârfuri și 48 de muchii , iar fiecare vârf are gradul 6. Fiecare pereche de noduri are exact doi vecini comuni, indiferent dacă perechea este sau nu conectată printr-o muchie.

Clădire

Graficul Shrikhande poate fi construit ca un grafic Cayley în care mulțimea de vârfuri este , iar două vârfuri sunt conectate dacă și numai dacă diferența este în .

Proprietăți

În graficul Shrikhand, oricare două vârfuri I și J au doi vecini comuni diferiți (excluzând vârfurile I și J înșiși ), ceea ce este adevărat indiferent dacă I ​​și J sunt adiacente sau nu. Cu alte cuvinte, graficul este puternic regulat și parametrii săi sunt: ​​{16,6,2,2}, adică . Din această egalitate rezultă că graficul este asociat cu proiecte de bloc incomplete simetrice echilibrate ( ing. Proiecte de blocuri incomplete echilibrate , BIBD). Graficul Shrikhande împărtășește acești parametri cu exact un alt grafic, graficul 4×4 rook , adică graficul cu linii L ( K 4,4 ) al graficului bipartit complet K 4,4 . Ultimul grafic este singurul grafic de linii L ( K n, n ) pentru care parametrii de regularitate puternică nu definesc în mod unic acest grafic, iar graficul îi împarte cu un alt grafic, și anume graficul Shrikhande (care nu este un grafic rook) [ 2] [3 ] .  

Graficul lui Srikhande este local hexagonal . Adică vecinii fiecărui vârf formează un ciclu de șase vârfuri. Ca orice graf ciclic local, graful Shrikhande este 1-scheletul triangulației Whitney a unei suprafețe. În cazul grafului Shrikhande, această suprafață este un tor , în care fiecare vârf este înconjurat de șase triunghiuri [4] Astfel, graful Shrikhande este un graf toroidal . Încorporarea formează o mapare regulată într-un tor cu 32 de fețe triunghiulare. Scheletul graficului dual al acestei mapări (încorporat într-un tor) este graficul Dyck , un grafic simetric cubic.

Graficul Shrikhande nu este tranzitiv la distanță . Acesta este cel mai mic grafic distanță-regular care nu este tranzitiv la distanță [5] .

Grupul de automorfism al grafului Shrikhande are ordinul 192. Acționează tranzitiv asupra vârfurilor, muchiilor și arcelor grafului. Prin urmare, graficul Shrikhande este un grafic simetric .

Polinomul caracteristic al graficului Shrikhande este . Astfel, graficul Shrikhande este un grafic întreg  - spectrul său este format în întregime din numere întregi.

Graficul are grosimea cărții 4 și numărul de cozi 3 [6] .

Galerie

• Graficul lui Srikhande este toroidal .

• Numărul cromatic al contelui Srikhande este 4.

• Indicele cromatic al contelui Shrikhande este 6.

• Contele de Srikhande, desenat simetric.

• Contele Srikhande din Hamilton .

Note

1. ^ Weisstein , Eric W. Shrikhande Graph  pe site- ul Wolfram MathWorld .
2. ↑ 1 2 Shrikhande, 1959 , p. 781–798.
3. ↑ Harary, 1972 , p. 79.
4. ↑ Graficul Brouwer AE Shrikhande Arhivat la 9 martie 2014 la Wayback Machine .
5. ↑ Brouwer, Cohen, Neumaier 1989 , p. 104–105, 136.
6. ↑ Volz, 2018 .

Literatură

• Shrikhande SS Unicitatea schemei de asociere L 2  // Annals of Mathematical Statistics. - 1959. - T. 30 . — S. 781–798 . - doi : 10.1214/aoms/1177706207 . — .
• Frank Harary. teoria grafurilor . — Massachusetts: Addison-Wesley, 1972.
  • Harari F. Teoria grafurilor. - 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. Proiectări liniare cu SAT. - Universitatea din Tübingen, 2018. - (Teză de master).

Link -uri

• The Shrikhande Graph Arhivat 24 noiembrie 2010 la Wayback Machine , Peter Cameron, august 2010.