Граф Берлекемпа ван Лінта Зейделя це локально лінійний регулярний граф з параметрами 243 22 1 2 тобто граф має 243 верши

Граф Берлекемпа — ван Лінта — Зейделя — це локально лінійний регулярний граф з параметрами (243,22,1,2), тобто, граф має 243 вершини, 22 ребра на вершину (загалом 2673 ребер), рівно одну спільну вершину для кожної пари суміжних вершин і рівно дві спільні вершини для будь-якої пари несуміжних. Граф побудували Елвін Берлекемп, ^[en] та Йохан Якоб Зайдель як ^[en]трійкових кодів Голея.

Властивості

Граф є графом Келі абелевої групи. Серед абелевих графів Келі, які строго регулярні і в яких останні два параметри відрізняються на одиницю, це єдиний граф, що не збігається з графом Пелі. Це також цілий граф, тобто, власні значення його матриці суміжності є цілими числами. Подібно до графа судоку $9\times 9$ він є цілим абелевим графом Келі, всі елементи групи якого мають порядок 3, одного з малих можливих чисел для порядків у таких графах.

Інші графи цього типу

Існує п'ять можливих комбінацій параметрів для сильно регулярних графів, які мають одну спільну вершину для кожної пари суміжних вершин і рівно два спільні сусіди для несуміжних вершин. З них відомо існування двох графів — це граф Берлекемпа — ван Лінта — Зейделя і граф Пелі з 9 вершинами з параметрами (9, 4, 1, 2). Задача Конвея про 99-вершинний граф запитує про існування іншого графа цього типу з параметрами (99,14,1,2).

Див. також

Граф Геймса

Примітки

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.
Arasu K. T., Jungnickel D., Ma S. L., Pott A. Strongly regular Cayley graphs with $\lambda -\mu =-1$ // . — 1994. — Т. 67, вип. 1. — С. 116–125. — DOI:10.1016/0097-3165(94)90007-8.
Weisstein, Eric W. Berlekamp-van Lint-Seidel Graph(англ.) на сайті Wolfram MathWorld.
Walter Klotz, Torsten Sander. Integral Cayley graphs over abelian groups // Electronic Journal of Combinatorics. — 2010. — Т. 17, вип. 1. — С. Research Paper 81, 13pp.
Makhnev A. A., Minakova I. M.,. On automorphisms of strongly regular graphs with parameters $\lambda =1$ , $\mu =2$ // Discrete Mathematics and Applications. — 2004. — Т. 14, вип. 2 (січень). — DOI:10.1515/156939204872374.
John H. Conway. Five $1,000 Problems (Update 2017). — Online Encyclopedia of Integer Sequences.

[bvls-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.

[ajmp-2] Arasu K. T., Jungnickel D., Ma S. L., Pott A. Strongly regular Cayley graphs with $\lambda -\mu =-1$ // . — 1994. — Т. 67, вип. 1. — С. 116–125. — DOI:10.1016/0097-3165(94)90007-8.

[mw-3] Weisstein, Eric W. Berlekamp-van Lint-Seidel Graph(англ.) на сайті Wolfram MathWorld.

[ks-4] Walter Klotz, Torsten Sander. Integral Cayley graphs over abelian groups // Electronic Journal of Combinatorics. — 2010. — Т. 17, вип. 1. — С. Research Paper 81, 13pp.

[mm-5] Makhnev A. A., Minakova I. M.,. On automorphisms of strongly regular graphs with parameters $\lambda =1$ , $\mu =2$ // Discrete Mathematics and Applications. — 2004. — Т. 14, вип. 2 (січень). — DOI:10.1515/156939204872374.

[con-6] John H. Conway. Five $1,000 Problems (Update 2017). — Online Encyclopedia of Integer Sequences.