Граф Берлекэмпа — ван Линта — Зейделя — это локально линейный сильно регулярный граф с параметрами (243,22,1,2), это означает, что граф имеет 243 вершины, 22 ребра на вершину (в общей сложности 2673 рёбер), в точности одну общую вершину для каждой пары смежных вершин и в точности две общие вершины для любой пары несмежных. Граф построили Элвин Берлекэмп, Дж. Г. ван Линт и Йохан Якоб Зайдель как троичных кодов Голея.
Свойства Граф является графом Кэли абелевой группы. Среди абелевых графов Кэли, которые строго регулярны и в которых последние два параметра отличаются на единицу, это единственный граф, не совпадающий с графом Пэли. Это также целый граф, это означает, что собственные значения его матрицы смежности являются целыми числами. Подобно графу судоку он является целым абелевым графом Кэли, все элементы группы которого имеют порядок 3, одного из малых возможных чисел для порядков в таких графах.
Другие графы этого типа Существует пять возможных комбинаций параметров для сильно регулярных графов, которые имеют одну общую вершину для каждой пары смежных вершин и в точности два общих соседа для несмежных вершин. Из них известно существование двух графов — это граф Берлекэмпа — ван Линта — Зейделя и граф Пэли с 9 вершинами с параметрами (9,4,1,2). Проблема Конвея 99-графа спрашивает о существовании другого графа этого типа с параметрами (99,14,1,2).
См. также Граф Геймса
Примечания
Категория:Сильно регулярные графы