Граф Берлекемпа — ван Лінта — Зейделя
Граф Берлекемпа — ван Лінта — Зейделя — це локально лінійний регулярний граф з параметрами (243,22,1,2), тобто, граф має 243 вершини, 22 ребра на вершину (загалом 2673 ребер), рівно одну спільну вершину для кожної пари суміжних вершин і рівно дві спільні вершини для будь-якої пари несуміжних. Граф побудували Елвін Берлекемп, Дж. Г. ван Лінт[en] та Йохан Якоб Зайдель як граф суміжності[en] трійкових кодів Голея[1].
Властивості[ред. | ред. код]
Граф є графом Келі абелевої групи. Серед абелевих графів Келі, які строго регулярні і в яких останні два параметри відрізняються на одиницю, це єдиний граф, що не збігається з графом Пелі[2]. Це також цілий граф, тобто, власні значення його матриці суміжності є цілими числами[3]. Подібно до графа судоку він є цілим абелевим графом Келі, всі елементи групи якого мають порядок 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 // 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.
- ↑ Makhnev A. A., Minakova I. M.,. On automorphisms of strongly regular graphs with parameters , // 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.
