Geodesic
$2$-Factors without close edges in~the~$n$-dimensional cube
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 5-26.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : $n$-dimensional hypercube
Keywords: perfect matching, $2$-factor. 
@article{DA_2019_26_3_a0,
     author = {I. S. Bykov},
     title = {$2${-Factors} without close edges in~the~$n$-dimensional cube},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--26},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_3_a0/}
}
TY  - JOUR
AU  - I. S. Bykov
TI  - $2$-Factors without close edges in~the~$n$-dimensional cube
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 5
EP  - 26
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_3_a0/
LA  - ru
ID  - DA_2019_26_3_a0
ER  - 
%0 Journal Article
%A I. S. Bykov
%T $2$-Factors without close edges in~the~$n$-dimensional cube
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 5-26
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_3_a0/
%G ru
%F DA_2019_26_3_a0
I. S. Bykov. $2$-Factors without close edges in~the~$n$-dimensional cube. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 5-26. http://geodesic.mathdoc.fr/item/DA_2019_26_3_a0/

[1] I. S. Bykov, “On locally balanced Gray codes”, J. Appl. Indust. Math., 10:1 (2016), 78–85 | DOI | MR | Zbl

[2] A. A. Evdokimov, “Chain of maximal length in a unitary $n$-dimensional cube”, Math. Notes, 6 (1969), 642–648 | DOI | MR

[3] D. S. Krotov, “Inductive construction of perfect ternary constant-weight codes with distance 3”, Problems Inform. Transmission, 37:1 (2001), 1–9 | DOI | MR | Zbl

[4] A. L. Perezhogin, “On locally isometric coding of natural numbers”, Diskretn. Anal. Issled. Oper., 3:4 (1996), 69–76 (Russian) | MR | Zbl

[5] A. L. Perezhogin, “On special perfect matchings in a Boolean cube”, Diskretn. Anal. Issled. Oper., Ser. 1, 12:4 (2005), 51–59 (Russian) | MR | Zbl

[6] A. L. Perezhogin, V. N. Potapov, “On the number of Hamiltonian cycles in a Boolean cube”, Diskretn. Anal. Issled. Oper., Ser. 1, 8:2 (2001), 52–62 (Russian) | MR | Zbl

[7] Fink J., “Perfect matchings extend to Hamilton cycles in hypercubes”, J. Comb. Theory, Ser. B, 97:6 (2007), 1074–1076 | DOI | MR | Zbl

[8] Goddyn L., Gvozdjak P., “Binary Gray codes with long bit runs”, Electron. J. Comb., 10 (2003) | MR | Zbl

[9] Gregor P., Mutze T., Nummenpalo J., “A short proof of the middle levels theorem”, Discrete Anal., 2018 | DOI | MR

[10] Kautz W. H., “Unit-distance error-checking codes”, IRE Trans. Electron. Comput., EC-7:2 (1958), 179–180 | DOI

[11] Van Zanten A. J., Haryanto L., “Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube”, Des. Codes Cryptogr., 48:3 (2008), 207–229 | DOI | MR | Zbl

[12] Zemor G., “An upper bound on the size of the snake-in-the-box”, Combinatorica, 17:2 (1997), 287–298 | DOI | MR | Zbl