Generalized Gray codes with prescribed ends (Q512653): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1603.08827 / rank | |||
Normal rank |
Revision as of 14:44, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalized Gray codes with prescribed ends |
scientific article |
Statements
Generalized Gray codes with prescribed ends (English)
0 references
27 February 2017
0 references
An \(n\)-bit Gray code is a sequence of all \(n\)-bit vectors such that consecutive vectors differ in a single bit. Given any two \(n\)-bit vectors \(\alpha\) and \(\beta\), there is a Gray code starting in \(\alpha\) and ending in \(\beta\) if and only if the Hamming distance \(d(\alpha,\beta)\) is odd; see [\textit{I. Havel}, Čas. Pěstování Mat. 109, 135--152 (1984; Zbl 0544.05057)] \textit{R. Caha} and \textit{V. Koubek} [Discrete Math. 307, 2053--2066 (2007; Zbl 1125.05054)] generalised this fact by defining any set of \(2k\) distinct \(n\)-bit vectors \(\alpha_1,\beta_1,\ldots,\alpha_k,\beta_k\) to be \textit{connectable} if there are \(k\) sequences of distinct \(n\)-bit vectors that partition the set of all \(n\)-bit vectors such that, for each \(i=1,\ldots,k\), the \(i\)th sequence leads from \(\alpha_i\) to \(\beta_i\) and its consecutive vectors differ in a single bit. Caha and Koubek proved that, for \(k\leq n/2\), each such set of \(k\) vectors is connectable exactly when \(d(\alpha_i,\beta_i)\) is odd for each \(i=1,\ldots,k\). The present authors improve this result by proving that it is also true more generally when \(k\leq n-1\). This is a best possible bound and improves previous partial improvements in the literature.
0 references
Gray code
0 references
Hamiltonian path
0 references
hypercube
0 references
path partition
0 references
disjoint path cover
0 references
prescribed endvertices
0 references