Граф Берлекампа – ван Линта – Зейделя - Berlekamp–van Lint–Seidel graph - Wikipedia

Два рисунка графа Берлекампа – ван Линта – Зейделя.

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

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

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

Смотрите также

• График игр

Рекомендации

1. Берлекамп, Э.; ван Линт, Дж. Х.; Зайдель, Дж. Дж. (1973), «Сильно регулярный граф, полученный из совершенного тернарного кода Голея» (PDF), Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), Амстердам: Северная Голландия: 25–30, Дои:10.1016 / B978-0-7204-2262-7.50008-9, МИСТЕР  0364015
2. Arasu, K. T .; Юнгникель, Д.; Ma, S. L .; Потт, A. (1994), "Сильно регулярные графы Кэли с ${\displaystyle \lambda -\mu =-1}$", Журнал комбинаторной теории, Серия А, 67 (1): 116–125, Дои:10.1016/0097-3165(94)90007-8, МИСТЕР  1280602
3. Вайсштейн, Эрик В. "График Берлекампа-ван Линта-Зейделя". MathWorld.
4. Клотц, Вальтер; Сандер, Торстен (2010), «Интегральные графы Кэли над абелевыми группами», Электронный журнал комбинаторики, 17 (1): Research Paper 81, 13pp, МИСТЕР  2651734
5. Махнев, А. А .; Минакова И. М. (январь 2004 г.) «Об автоморфизмах сильно регулярных графов с параметрами. ${\displaystyle \lambda =1}$, ${\displaystyle \mu =2}$", Дискретная математика и приложения, 14 (2), Дои:10.1515/156939204872374, МИСТЕР  2069991
6. Конвей, Джон Х., Пять проблем по 1000 долларов (обновление 2017 г.) (PDF), Интернет-энциклопедия целочисленных последовательностей, получено 2019-02-12