On the spectrum of Hamiltonian cycles in the n-cube Full article
| Journal |
Journal of Combinatorial Theory. Series B
ISSN: 0095-8956 , E-ISSN: 1096-0902 |
||
|---|---|---|---|
| Output data | Year: 2021, Volume: 151, Pages: 435-464 Pages count : 30 DOI: 10.1016/j.jctb.2021.08.002 | ||
| Tags | Boolean cube; Edge direction spectrum; Gray code; Hamiltonian cycle | ||
| Authors |
|
||
| Affiliations |
|
Abstract:
The spectrum of a Hamiltonian cycle (Gray code) in a Boolean n-cube is a sequence of n numbers, where the ith number is equal to the number of edges of the ith direction in the cycle. Necessary conditions for the existence of a Gray code with a given spectrum are known: all numbers are even and the sum of any k numbers is at least 2k, k=1,…,n. It is proved that for all dimensions n these necessary conditions are sufficient for the existence of a Gray code with the given spectrum. © 2021 Elsevier Inc.
Cite:
Perezhogin A.L.
On the spectrum of Hamiltonian cycles in the n-cube
Journal of Combinatorial Theory. Series B. 2021. V.151. P.435-464. DOI: 10.1016/j.jctb.2021.08.002 WOS Scopus РИНЦ OpenAlex
On the spectrum of Hamiltonian cycles in the n-cube
Journal of Combinatorial Theory. Series B. 2021. V.151. P.435-464. DOI: 10.1016/j.jctb.2021.08.002 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Sep 9, 2020 |
| Published online: | Aug 27, 2021 |
Identifiers:
| Web of science: | WOS:000702280800018 |
| Scopus: | 2-s2.0-85113497712 |
| Elibrary: | 46958895 |
| OpenAlex: | W3196332366 |