Том 26, номер 3, 2019 г., Стр. 5-26

УДК 519.17
Быков И. С.
2-Факторы без близких рёбер в $n$-мерном кубе

Аннотация:
Назовём два ребра гиперкуба близкими, если их концы образуют подкуб размерности 2. Рассматривается задача построения 2-фактора, не содержащего близких рёбер, в графе гиперкуба. Для решения данной задачи используется новая конструкция построения 2-факторов, которая обобщает известную ранее потоковую конструкцию гамильтоновых циклов в гиперкубе. С помощью этой конструкции удалось построить семейство 2-факторов без близких рёбер в кубах всех размерностей, начиная с 10, при этом длины циклов в полученных 2-факторах увеличиваются с ростом размерности.
Табл. 5, библиогр. 12.

Ключевые слова: $n$-мерный гиперкуб, совершенное паросочетание, 2-фактор.

DOI: 10.33048/daio.2019.26.641

Быков Игорь Сергеевич ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: patrick.no10@gmail.com

Статья поступила 23 ноября 2018 г.
После доработки — 29 марта 2019 г.
Принята к публикации 5 июня 2019 г.

Литература

[1] Быков И. С. О локально равномерных кодах Грея // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 1. С. 51–64.

[2] Евдокимов А. А. О максимальной длине цепи в единичном $n$-мерном кубе // Мат. заметки. 1969. Т. 4, Вып. 3. С. 309–319.

[3] Кротов Д. С. Индуктивные конструкции совершенных троичных равновесных кодов с расстоянием 3 // Пробл. передачи информации. 2001. Т. 37, № 1. С. 3–11.

[4] Пережогин А. Л. О локально изометрическом кодировании натуральных чисел // Дискрет. анализ и исслед. операций. 1996. Т. 3, № 4. С. 69–76.

[5] Пережогин А. Л. О специальных совершенных паросочетаниях в булевом кубе // Дискрет. анализ и исслед. операций. 2005. Т. 12, № 4. С. 51–59.

[6] Пережогин А. Л., Потапов В. Н. О числе гамильтоновых циклов в булевом кубе // Дискрет. анализ и исслед. операций. 2001. Т. 8, № 2. С. 52–62.

[7] Fink J. Perfect matchings extend to Hamilton cycles in hypercubes // J. Comb. Theory, Ser. B. 2007. Vol. 97, No. 6. P. 1074–1076.

[8] Goddyn L., Gvozdjak P. Binary Gray codes with long bit runs // Electron. J. Comb. 2003. No. 10.

[9] Gregor P., Mutze T., Nummenpalo J. A short proof of the middle levels theorem // Discrete Anal. 2018. Published online at http://dx.doi.org/10.19086/da.3659.

[10] Kautz W. H. Unit-distance error-checking codes // IRE Trans. Electron. Comput. 1958. Vol. EC-7, No. 2. P. 179–180.

[11] Van Zanten A. J., Haryanto L. Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube // Des. Codes Cryptogr. 2008. Vol. 48, No. 3. P. 207–229.

[12] Zemor G. An upper bound on the size of the snake-in-the-box // Combinatorica. 1997. Vol. 17, No. 2. P. 287–298.