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

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

Свойства

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

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

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

См. также

Граф Геймса

Примечания

↑ 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$ // Journal of Combinatorial Theory. — 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. Архивировано 14 апреля 2011 года.
↑ 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. Архивировано 13 февраля 2019 года.

[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$ // Journal of Combinatorial Theory. — 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. Архивировано 14 апреля 2011 года.

[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. Архивировано 13 февраля 2019 года.

[1]

[2]

[3]

[4]

[5]

[6]