Generalized Gray codes with prescribed ends

DOI10.1016/J.TCS.2017.01.010MaRDI QIDQ512653zbMATH OpenOpenAlexFDO

Authors Tomáš Dvořák, Petr Gregor, Václav Koubek

Publication date 27 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.08827

zbMATH Keywords

disjoint path cover Gray code Hamiltonian path hypercube path partition prescribed endvertices

Mathematics Subject Classification ID

Combinatorial codes (94B25)

Abstract: An

n

-bit Gray code is a sequence of all

n

-bit strings such that consecutive strings differ in a single bit. It is well-known that given

, an

n

-bit Gray code between

a l p h a

and

exists iff the Hamming distance

of

a l p h a

and

is odd. We generalize this classical result to

k

pairwise disjoint pairs

: if

is odd for all

i

and

k < n

, then the set of all

n

-bit strings can be partitioned into

k

sequences such that the

i

-th sequence leads from

a l p h a_{i}

to

and consecutive strings differ in a single bit. This holds for every

n > 1

with one exception in the case when

n = k + 1 = 4

. Our result is optimal in the sense that for every

n > 2

there are

n

pairwise disjoint pairs

with

odd for which such sequences do not exist.

Review text

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.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: Generalized Gray codes with prescribed ends

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512653)