Граф Берлекемпа — ван Лінта — Зейделя — це локально лінійний регулярний граф з параметрами (243,22,1,2), тобто, граф має 243 вершини, 22 ребра на вершину (загалом 2673 ребер), рівно одну спільну вершину для кожної пари суміжних вершин і рівно дві спільні вершини для будь-якої пари несуміжних. Граф побудували Елвін Берлекемп, та Йохан Якоб Зайдель як трійкових кодів Голея.
Властивості Граф є графом Келі абелевої групи. Серед абелевих графів Келі, які строго регулярні і в яких останні два параметри відрізняються на одиницю, це єдиний граф, що не збігається з графом Пелі. Це також цілий граф, тобто, власні значення його матриці суміжності є цілими числами. Подібно до графа судоку він є цілим абелевим графом Келі, всі елементи групи якого мають порядок 3, одного з малих можливих чисел для порядків у таких графах.
Інші графи цього типу Існує п'ять можливих комбінацій параметрів для сильно регулярних графів, які мають одну спільну вершину для кожної пари суміжних вершин і рівно два спільні сусіди для несуміжних вершин. З них відомо існування двох графів — це граф Берлекемпа — ван Лінта — Зейделя і граф Пелі з 9 вершинами з параметрами (9, 4, 1, 2). Задача Конвея про 99-вершинний граф запитує про існування іншого графа цього типу з параметрами (99,14,1,2).
Див. також
Граф Геймса
Примітки