Том 15, номер 5, 2008 г., Стр. 35-46

УДК 519.174
Д. С. Кротов
О совершенных раскрасках половинного 24-куба

Аннотация:
Раскраска вершин графа называется совершенной с параметрами $(a_{ij})_{i,j=1}^k$, если для всех $i$ и $j$ от 1 до $k$ каждая вершина цвета $i$ смежна ровно с $a_{ij}$ вершинами цвета $j$. Рассматриваются совершенные раскраски в два цвета графа расстояний 2 гиперкуба $\{0,1\}^{24}$ с параметрами $((20+c,256-c)(c,276-c))$ (т.е. с собственным значением 20). Доказано, что такие раскраски существуют при всех $c$ от 1 до 128, кроме 1, 2, 4, 5, 7, 10, 13, и не существуют при $c=1,2,4,5,7$.
Табл. 2, библиогр. 4.

Ключевые слова: совершенная раскраска, половинчатый гиперкуб.

Кротов Денис Станиславович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: krotov@math.nsc.ru

Статья поступила 18 марта 2008 г.