×

Generalized Gray codes with prescribed ends. (English) Zbl 1367.94402

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 [I. Havel, Čas. Pěstování Mat. 109, 135–152 (1984; Zbl 0544.05057)]
R. Caha and 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 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.

MSC:

94B25 Combinatorial codes
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bollobás, B., Modern Graph Theory (2013), Springer
[2] Caha, R.; Koubek, V., Spanning multi-paths in hypercubes, Discrete Math., 307, 2053-2066 (2007) · Zbl 1125.05054
[3] Castañeda, N.; Gotchev, I., Path coverings with prescribed ends in faulty hypercubes, Graphs Combin., 31, 833-869 (2015) · Zbl 1317.05101
[4] Castañeda, N.; Gotchev, I.; Gotchev, V.; Latour, F., Path coverings with prescribed ends of the \(n\)-dimensional binary hypercube, Congr. Numer., 197, 193-205 (2009) · Zbl 1206.05056
[5] Castañeda, N.; Gotchev, I.; Gotchev, V.; Latour, F., On path coverings of hypercubes with one faulty vertex, Graph Theory Notes N. Y., LVIII, 42-47 (2010)
[6] Chen, X.-B., Paired many-to-many disjoint path covers of the hypercubes, Inform. Sci., 236, 218-223 (2013) · Zbl 1284.05274
[7] Dvořák, T., Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math., 19, 135-144 (2005) · Zbl 1082.05056
[8] Dvořák, T.; Gregor, P., Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM J. Discrete Math., 22, 1448-1461 (2008) · Zbl 1187.05056
[9] Dvořák, T.; Gregor, P.; Koubek, V., Spanning paths in hypercubes, Discrete Math. Theor. Comput. Sci. AE, 363-368 (2005) · Zbl 1192.05077
[10] Dvořák, T.; Koubek, V., Generalized Gray codes with prescribed ends of small dimensions
[11] Dvořák, T.; Koubek, V., Computational complexity of long paths and cycles in faulty hypercubes, Theoret. Comput. Sci., 411, 3774-3786 (2010) · Zbl 1207.68038
[12] Gregor, P.; Dvořák, T., Path partitions of hypercubes, Inform. Process. Lett., 108, 402-406 (2008) · Zbl 1191.68037
[13] Havel, I., On hamiltonian circuits and spanning trees of hypercubes, Čas. Pěst. Mat., 109, 135-152 (1984) · Zbl 0544.05057
[14] Jo, S.; Park, J.-H.; Chwa, K.-Y., Paired many-to-many disjoint path covers in faulty hypercubes, Theoret. Comput. Sci., 513, 1-24 (2013) · Zbl 1352.68195
[15] Knuth, D. E., The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (2005), Addison-Wesley Professional · Zbl 1127.68068
[16] Lewinter, M.; Widulski, W., Hyper-Hamilton laceable and caterpillar-spannable product graphs, Comput. Math. Appl., 34, 99-104 (1997) · Zbl 0907.05033
[17] Savage, C., A survey of combinatorial Gray codes, SIAM Rev., 39, 605-629 (1997) · Zbl 1049.94513
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.