Greve av Berlekamp-van Lint-Seidel

Berlekamp-van Lint-Seidel- grafen är en lokalt linjär starkt regelbunden graf med parametrar (243,22,1,2), vilket innebär att grafen har 243 hörn, 22 kanter per vertex (för totalt 2673 kanter), exakt en gemensam vertex för varje par av angränsande hörn, och exakt två gemensamma hörn för alla par av icke-angränsande. Grafen konstruerades av Alvin Berlekamp , J. G. van Lint och Johan Jakob Seidel som en närliggande graf av ternära Golay-koder [1] .

Egenskaper

Grafen är Cayley-grafen för den abelska gruppen . Bland Abelian Cayley-grafer som är strikt regelbundna och där de två sista parametrarna skiljer sig åt med en, är detta den enda grafen som inte är densamma som Paley-grafen [2] . Det är också en heltalsgraf , vilket betyder att egenvärdena för dess närliggande matris är heltal [3] . Liksom en Sudoku-graf är det en hel Abelian Cayley-graf, vars alla gruppelement har ordning 3, ett av de minsta möjliga siffrorna för beställningar i sådana grafer [4] .

Andra grafer av denna typ

Det finns fem möjliga kombinationer av parametrar för starkt regelbundna grafer som har en gemensam vertex för varje par av angränsande hörn, och exakt två gemensamma grannar för icke-intilliggande hörn. Av dessa är det känt att det finns två grafer - det här är Berlekamp-van Lint-Seidel-grafen och Paley-grafen med 9 hörn med parametrar (9,4,1,2) [5] . Conways 99-grafproblem frågar om det finns en annan graf av denna typ med parametrar (99,14,1,2) [6] .

Se även

Anteckningar

  1. ↑ Berlekamp ER, van Lint JH, Seidel JJ En starkt regelbunden graf härledd från den perfekta ternära Golay-koden // A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Nord-Holland, 1973. - S. 25-30 . - doi : 10.1016/B978-0-7204-2262-7.50008-9 .
  2. ↑ Arasu KT, Jungnickel D., Ma SL, Pott A. Starkt regelbundna Cayley-grafer med  // Journal of Combinatorial Theory . - 1994. - T. 67 , nr. 1 . — S. 116–125 . - doi : 10.1016/0097-3165(94)90007-8 .
  3. ↑ Weisstein, Eric W. Berlekamp-van Lint-Seidel Graph  på Wolfram MathWorld -webbplatsen .
  4. ↑ Walter Klotz, Torsten Sander. Integral Cayley-grafer över abelska grupper  // Electronic Journal of Combinatorics. - 2010. - T. 17 , nr. 1 . — C. Forskningsuppsats 81, 13pp .
  5. ↑ Makhnev AA, Minakova IM,. Om automorfismer av starkt regelbundna grafer med parametrar ,  // Diskret matematik och applikationer. - 2004. - Januari ( vol. 14 , nummer 2 ). - doi : 10.1515/156939204872374 .
  6. ↑ John H. Conway. Fem $1 000-problem (uppdatering 2017) . — Online Encyclopedia of Integer Sequences.