Граф Берлекэмпа — ван Линта — Зейделя

Граф Берлекэмпа — ван Линта — Зейделя — это локально линейный сильно регулярный граф с параметрами (243,22,1,2), это означает, что граф имеет 243 вершины, 22 ребра на вершину (в общей сложности 2673 рёбер), в точности одну общую вершину для каждой пары смежных вершин и в точности две общие вершины для любой пары несмежных. Граф построили Элвин Берлекэмп, Дж. Г. ван Линт и Йохан Якоб Зайдель как граф смежности троичных кодов Голея[1].

Свойства

Граф является графом Кэли абелевой группы. Среди абелевых графов Кэли, которые строго регулярны и в которых последние два параметра отличаются на единицу, это единственный граф, не совпадающий с графом Пэли[2]. Это также целый граф, это означает, что собственные значения его матрицы смежности являются целыми числами[3]. Подобно графу судоку он является целым абелевым графом Кэли, все элементы группы которого имеют порядок 3, одного из малых возможных чисел для порядков в таких графах[4].

Другие графы этого типа

Существует пять возможных комбинаций параметров для сильно регулярных графов, которые имеют одну общую вершину для каждой пары смежных вершин и в точности два общих соседа для несмежных вершин. Из них известно существование двух графов — это граф Берлекэмпа — ван Линта — Зейделя и граф Пэли с 9 вершинами с параметрами (9,4,1,2)[5]. Проблема Конвея 99-графа спрашивает о существовании другого графа этого типа с параметрами (99,14,1,2)[6].

См. также

Примечания
  1. Berlekamp E. R., van Lint J. H., Seidel J. J. A strongly regular graph derived from the perfect ternary Golay code // A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). — North-Holland, 1973. — С. 25–30. — doi:10.1016/B978-0-7204-2262-7.50008-9.
  2. Arasu K. T., Jungnickel D., Ma S. L., Pott A. Strongly regular Cayley graphs with  // Journal of Combinatorial Theory. — 1994. — Т. 67, вып. 1. — С. 116–125. — doi:10.1016/0097-3165(94)90007-8.
  3. Weisstein, Eric W. Berlekamp-van Lint-Seidel Graph (англ.) на сайте Wolfram MathWorld.
  4. Walter Klotz, Torsten Sander. Integral Cayley graphs over abelian groups // Electronic Journal of Combinatorics. — 2010. — Т. 17, вып. 1. — С. Research Paper 81, 13pp.
  5. Makhnev A. A., Minakova I. M.,. On automorphisms of strongly regular graphs with parameters ,  // Discrete Mathematics and Applications. — 2004. — Январь (т. 14, вып. 2). — doi:10.1515/156939204872374.
  6. John H. Conway. Five $1,000 Problems (Update 2017). — Online Encyclopedia of Integer Sequences.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.