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

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

Свойства

Граф является графом Кэли абелевой группы. Среди абелевых графов Кэли, которые строго регулярны и в которых последние два параметра отличаются на единицу, это единственный граф, не совпадающий с графом ПэлиШаблон:R. Это также целый граф, это означает, что собственные значения его матрицы смежности являются целыми числамиШаблон:R. Подобно $9\times 9$ графу судоку он является целым абелевым графом Кэли, все элементы группы которого имеют порядок 3, одного из малых возможных чисел для порядков в таких графахШаблон:R.

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

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

См. также

• Граф Геймса