Abstract
Let k be a positive integer. A sequence s over an n-element alphabet A is called a k-radius sequence if every two symbols from A occur in s at distance of at most k. Let f k(n) denote the length of a shortest k-radius sequence over A. We provide constructions demonstrating that (1) for every fixed k and for every fixed ε>0, f k(n)=1/2k n 2+O(n 1+ε) and (2) for every k=n α, where α is a fixed real such that 0<α<1, f k(n)=1/2k n 2+O(n β), for some β<2-α. Since f k(n)≥ 1/2k n 2-n/2k, the constructions give asymptotically optimal k-radius sequences. Finally, (3) we construct optimal 2-radius sequences for a 2p-element alphabet, where p is a prime.
Original language | English |
---|---|
Pages (from-to) | 731-746 |
Number of pages | 16 |
Journal | Journal of Combinatorial Theory. Series A |
Volume | 119 |
Issue number | 3 |
DOIs | |
State | Published - Apr 2012 |
Bibliographical note
Funding Information:E-mail addresses: [email protected] (J.W. Jaromczyk), [email protected] (Z. Lonc), [email protected] (M. Truszczyński). 1 Supported by the European Union in the framework of European Social Fund through the Warsaw University of Technology Development Programme.
Keywords
- Cycle decompositions of graphs
- K-radius sequences
- Universal cycles
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics