Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:3, 405-417
Volume 26, No 3, 2019, P. 5-26
UDC 519.17
I. S. Bykov
2-Factors without close edges in the $n$-dimensional cube
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.
DOI: 10.33048/daio.2019.26.641
Igor S. Bykov 1
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: patrick.no10@gmail.com
Received November 23, 2018
Revised March 29, 2019
Accepted June 5, 2019
References
[1] I. S. Bykov, On locally balanced Gray codes, Diskretn. Anal. Issled. Oper. 23 (1), 51–64 (2016) [Russian] [J. Appl. Indust. Math. 10 (1), 78–85 (2016)].[2] A. A. Evdokimov, Chain of maximal length in a unitary $n$-dimensional cube, Mat. Zametki 6, 309–319 (1969) [Russian] [Math. Notes 6, 642–648 (1969)].
[3] D. S. Krotov, Inductive construction of perfect ternary constant-weight codes with distance 3, Problemy Peredachi Inform. 37 (1), 3–11 (2001) [Russian] [Problems Inform. Transmission 37 (1), 1–9 (2001)].
[4] A. L. Perezhogin, On locally isometric coding of natural numbers, Diskretn. Anal. Issled. Oper. 3 (4), 69–76 (1996) [Russian].
[5] A. L. Perezhogin, On special perfect matchings in a Boolean cube, Diskretn. Anal. Issled. Oper., Ser. 1, 12 (4), 51–59 (2005) [Russian].
[6] A. L. Perezhogin and V. N. Potapov, On the number of Hamiltonian cycles in a Boolean cube, Diskretn. Anal. Issled. Oper., Ser. 1, 8 (2), 52–62 (2001) [Russian].
[7] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory, Ser. B, 97 (6), 1074–1076 (2007).
[8] L. Goddyn and P. Gvozdjak, Binary Gray codes with long bit runs, Electron. J. Combin. 10 (2003).
[9] P. Gregor, T. Mutze, and J. Nummenpalo, A short proof of the middle levels theorem, Discrete Analysis (2018). Published online at http://dx.doi.org/10.19086/da.3659.
[10] W. H. Kautz, Unit-distance error-checking codes, IRE Trans. Electronic Computers EC-7, 179–180 (1958).
[11] A. J. van Zanten and L. Haryanto, Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube, Des. Codes Cryptogr. 48 (3), 207–229 (2008).
[12] G. Zemor, An upper bound on the size of the snake-in-the-box, Combinatorica 17 (2), 287–298 (1997).
