Abstract | ||
---|---|---|
A (kn;n)k-de Bruijn Cycle is a cyclic k-ary sequence with the property that every k-ary n-tuple appears exactly once contiguously on the cycle. A (kr, ks; m, n)k-de Bruijn Torus is a k-ary krXks toroidal array with the property that every k-ary m x n matrix appears exactly once contiguously on the torus. As is the case with de Bruijn cycles, the 2-dimensional version has many interesting applications, from coding and communications to pseudo-random arrays, spectral imaging, and robot self-location. J.C. Cock proved the existence of such tori for all m, n, and k, and Chung, Diaconis, and Graham asked if it were possible that r = s and m -= n for n even. Fan, Fan, Ma and Siu showed this was possible for k - 2. Combining new techniques with old, we prove the result for k |
Year | DOI | Venue |
---|---|---|
1993 | 10.1016/0097-3165(93)90087-O | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
k-ary krxks,k-de bruijn cycle,de bruijn cycle,cyclic k-ary sequence,de bruijn torus problem,j.c. cock,k-de bruijn torus,k-ary m,k-ary n-tuple,2-dimensional version,interesting application,2 dimensional,spectral imaging | Discrete mathematics,Combinatorics,Matrix (mathematics),De Bruijn torus,Torus,De Bruijn graph,De Bruijn sequence,Mathematics | Journal |
Volume | Issue | ISSN |
64 | 1 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
17 | 1.18 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Glenn Hurlbert | 1 | 136 | 19.35 |
Garth Isaak | 2 | 172 | 24.01 |