В теории графов , то графы Берлекемпа-Ван Lint-Зейделя являются локально линейным сильно регулярным графом с параметрами. Это означает, что он имеет 243 вершины, 22 ребра на вершину (всего 2673 ребра), ровно один общий сосед на пару смежных вершин и ровно два общих соседа на пару несмежных вершин. Он был построен Элвин Берликамп , JH ван Линт , и Йохан Якоб Зейделя как класс смежности графа из троичного кода Голея . [1]
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/1/15/The_Berlekamp-van_Lint-Seidel_Graph.png/460px-The_Berlekamp-van_Lint-Seidel_Graph.png)
Этот граф является графом Кэли из абелевой группы . Среди абелевых графов Кэли, которые являются сильно регулярными и у которых два последних параметра отличаются на один, это единственный граф, который не является графом Пэли . [2] Это также интегральный граф , что означает, что собственные значения его матрицы смежности являются целыми числами. [3] Как Граф судоку - это интегральный абелев граф Кэли, все элементы группы которого имеют порядок 3, одну из небольшого числа возможных порядков в таком графе. [4]
Существует пять возможных комбинаций параметров для строго регулярных графов, у которых есть один общий сосед на пару смежных вершин и ровно два общих соседа на пару несмежных вершин. Известно, что существуют два из них: граф Берлекампа – Ван Линта – Зейделя и 9-вершинный граф Пэли с параметрами. [5] Проблема 99-графа Конвея касается существования другого из этих графов, имеющего параметры.. [6]
Смотрите также
Рекомендации
- ^ Берлекамп, ER ; Ван Линт, Дж. Х . ; Зайдель, Дж. Дж. (1973), "Сильно регулярный граф, полученный из совершенного тернарного кода Голея" (PDF) , Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) Амстердам: Северная Голландия: 25-30, DOI : 10.1016 / B978-0-7204-2262-7.50008-9 , MR 0364015
- ^ Arasu, KT; Юнгникель, Д .; Ma, SL; Потт, А. (1994), "Сильно регулярные графы Кэли с», Журнал комбинаторной теории , Series A, 67 (1): 116-125, DOI : 10,1016 / 0097-3165 (94) 90007-8 , МР 1280602
- ^ Вайсштейн, Эрик В. "График Берлекампа – Ван Линта-Зейделя" . MathWorld .
- ^ Клотц, Вальтер; Сандер, Торстен (2010), «Интегральные графы Кэли над абелевыми группами» , Электронный журнал комбинаторики , 17 (1): Research Paper 81, 13pp, MR 2651734
- ^ Махнев А.А.; Минакова И.М. (январь 2004 г.) «Об автоморфизмах сильно регулярных графов с параметрами., », Дискретная математика и приложения , 14 (2), DOI : 10,1515 / 156939204872374 , MR 2069991
- ^ Конвей, Джон Х. , Five $ 1,000 Problems (Update 2017) (PDF) , Online Encyclopedia of Integer Sequences , получено 12 февраля 2019 г.