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

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

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

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

Существует пять возможных комбинаций параметров для строго регулярных графов, у которых есть один общий сосед на пару смежных вершин и ровно два общих соседа на пару несмежных вершин. Известно, что существуют два из них: граф Берлекампа – ван Линта – Зейделя и 9-вершинный граф Пэли с параметрами .[5] 99-графовая проблема Конвея касается существования другого из этих графов, с параметрами .[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), "Сильно регулярные графы Кэли с ", Журнал комбинаторной теории, Серия А, 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 г.) «Об автоморфизмах сильно регулярных графов с параметрами. , ", Дискретная математика и приложения, 14 (2), Дои:10.1515/156939204872374, МИСТЕР  2069991
  6. ^ Конвей, Джон Х., Пять проблем по 1000 долларов (обновление 2017 г.) (PDF), Интернет-энциклопедия целочисленных последовательностей, получено 2019-02-12