## 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: jurek@cs.uky.edu (J.W. Jaromczyk), zblonc@mini.pw.edu.pl (Z. Lonc), mirek@cs.uky.edu (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