Том 19, номер 4, 2012 г., Стр. 60-65

УДК 519.174
Воробьёв К. В. 
Кратные совершенные коды в гиперкубе

Аннотация:
Подмножество вершин графа называется k-кратным совершенным кодом радиуса r, если для каждой вершины шар радиуса r с центром в этой вершине содержит в точности k кодовых вершин. Получен критерий, который по параметрам совершенной 2-раскраски двоичного n-куба определяет, является ли она кратным совершенным кодом заданного радиуса r ≥ 1 некоторой кратности.
Библиогр. 13.

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

Воробьёв Константин Васильевич ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: konstantin.vorobev@gmail.com

Статья поступила 29 августа 2011 г.

Литература

[1] Воробьев К. В., Фон-Дер-Флаасс Д. Г. О совершенных 2-раскрасках гиперкуба // Сиб. электрон. мат. изв. — 2010. — Т. 7. — С. 67–75.

[2] Зиновьев В. А., Леонтьев В. К. О совершенных кодах // Препринт / ИППИ АН СССР. — 1972. — Т. 1. — С. 26–35.

[3] Кротов Д. С. О совершенных раскрасках половинного 24-куба // Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 5. — С. 35–46.

[4] Потапов В. Н. О совершенных раскрасках булева $n$-куба и корреляционно-иммунных функциях малой плотности // Сиб. электрон. мат. изв. — 2010. — Т. 7. — С. 372–382.

[5] Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски 12-мерного куба, достигающие границы корреляционной иммунности // Сиб. электрон. мат. изв. — 2007. — Т. 4. — С. 292–295.

[6] Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски гиперкуба // Сиб. мат. журн. — 2007. — Т. 48, № 4. — С. 923–930.

[7] Cohen G. D., Honkala I. S., Litsyn S. N., Lobstein A. C. Covering codes. — Amsterdam: Elsevier, 1997. — 542 p.

[8] Fon-Der-Flaass D. G. A bound on correlation immunity // Sib. Electron. Math. Reports. — 2007. — Т. 4. — С. 133–135.

[9] Habsieger L. Integer zeros of $q$-Krawtchouk polynomials in classical combinatorics // J. Adv. Appl. Math. — 2001. — Vol. 27, N 2–3. — P. 427–437.

[10] Krasikov I., Litsyn S. On integral zeros of Krawtchouk polynomials // J. Comb. Theory, Ser. A. — 1996. — Vol. 74, N 1. — P. 71–99.

[11] Nagell T. The Diophantine equation $x^{2} + 7 = 2^n$ // Ark. Mat. — 1960. — Vol. 4, N 2–3. — P. 185–187.

[12] Tietavainen A. On the nonexistence of perfect codes over the finite fields // SIAM J. Appl. Math. — 1973. — Vol. 24. — P. 88–96.

[13] VanWee G. J. M., Cohen G. D., Litsyn S. N. A note on perfect multiple coverings of the Hamming space // IEEE Trans. Inf. Theory. — 1991. — Vol. 37, N 3. — P. 678–682.