RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2019 Volume 26, Issue 3, Pages 5–26 (Mi da928)

$2$-Factors without close edges in the $n$-dimensional cube

I. S. Bykov

Novosibirsk State University, 1 Pirogov Street, 630090 Novosibirsk, Russia

Abstract: We say that two edges in the hypercube are close if their endpoints form a 2-dimensional subcube. We consider the problem of constructing a 2-factor not containing close edges in the hypercube graph. For solving this problem, we use the new construction for building 2-factors which generalizes the previously known stream construction for Hamiltonian cycles in a hypercube. Owing to this construction, we create a family of 2-factors without close edges in cubes of all dimensions starting from $10$, where the length of the cycles in the obtained 2-factors grows together with the dimension. Tab. 5, bibliogr. 12.

Keywords: $n$-dimensional hypercube, perfect matching, $2$-factor.

UDC: 519.17

Received: 23.11.2018
Revised: 29.03.2019
Accepted: 05.06.2019

DOI: 10.33048/daio.2019.26.641


 English version:
Journal of Applied and Industrial Mathematics, 2019, 13:3, 405–417

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024