Berlekamp-van Lint-Seidelin kreivi

Berlekamp-van Lint-Seidel- graafi on paikallisesti lineaarinen vahvasti säännöllinen graafi parametrein (243,22,1,2), mikä tarkoittaa, että graafissa on 243 kärkeä, 22 reunaa kärkeä kohti (yhteensä 2673 reunaa), täsmälleen yksi yhteinen kärki jokaiselle vierekkäisten pisteiden parille ja täsmälleen kaksi yhteistä kärkeä mille tahansa ei-viereisten kärkien parille. Graafin ovat rakentaneet Alvin Berlekamp , ​​J. G. van Lint ja Johan Jakob Seidel kolminkertaisten Golay-koodien vierekkäisyysgraafiksi 1] .

Ominaisuudet

Graafi on Abelin ryhmän Cayleyn graafi . Abelin Cayley-graafien joukossa, jotka ovat ehdottoman säännöllisiä ja joissa kaksi viimeistä parametria eroavat yhdellä, tämä on ainoa graafi, joka ei ole sama kuin Paley-graafi [2] . Se on myös kokonaislukukaavio , mikä tarkoittaa, että sen vierekkäisyysmatriisin ominaisarvot ovat kokonaislukuja [3] . Kuten Sudoku-graafi , se on kokonainen Abelin Cayleyn graafi, jonka kaikkien ryhmän elementtien luokka on 3, yksi pienimmistä mahdollisista järjestysluvuista sellaisissa kaavioissa [4] .

Muut tämän tyyppiset kaaviot

Voimakkaasti säännöllisille graafille on olemassa viisi mahdollista parametriyhdistelmää, joilla on yksi yhteinen kärki jokaista vierekkäistä pisteparia kohden ja täsmälleen kaksi yhteistä naapuria ei-viereisille pisteille. Näistä tunnetaan kahden graafin olemassaolo - tämä on Berlekamp-van Lint-Seidel-graafi ja Paley-graafi, jossa on 9 kärkeä parametrein (9,4,1,2) [5] . Conwayn 99-grafiikkatehtävä kysyy toisen tämäntyyppisen graafin olemassaolosta parametreilla (99,14,1,2) [6] .

Katso myös

Muistiinpanot

  1. ↑ Berlekamp ER, van Lint JH, Seidel JJ Täydellisestä kolmiosaisesta Golay-koodista johdettu vahvasti säännöllinen graafi // Tutkimus kombinatorisesta teoriasta (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Pohjois-Hollanti, 1973. - S. 25-30 . - doi : 10.1016/B978-0-7204-2262-7.50008-9 .
  2. ↑ Arasu KT, Jungnickel D., Ma SL, Pott A. Voimakkaasti säännölliset Cayley-kaaviot  // Journal of Combinatorial Theory . - 1994. - T. 67 , no. 1 . — S. 116–125 . - doi : 10.1016/0097-3165(94)90007-8 .
  3. ↑ Weisstein, Eric W. Berlekamp-van Lint-Seidel Graph  Wolfram MathWorld -verkkosivustolla .
  4. ↑ Walter Klotz, Torsten Sander. Integral Cayley kuvaajat Abelin ryhmien yli  // Electronic Journal of Combinatorics. - 2010. - T. 17 , no. 1 . — C. Tutkimuspaperi 81, 13 s .
  5. ↑ Makhnev AA, Minakova IM,. Vahvasti säännöllisten parametrien kuvaajien automorfismista ,  // Discrete Mathematics and Applications. - 2004. - tammikuu ( osa 14 , numero 2 ). - doi : 10.1515/156939204872374 .
  6. ↑ John H. Conway. Viisi 1 000 dollarin ongelmaa (päivitys 2017) . — Online Encyclopedia of Integer Sequences.