Sequences of radius [formula omitted] for complete bipartite graphs.

A k -radius sequence for a graph G is a sequence of vertices of G (typically with repetitions) such that for every edge u v of G vertices u and v appear at least once within distance k in the sequence. The length of a shortest k -radius sequence for G is denoted by f k ( G ) . We give an asymptotically tight estimation on f k ( G ) for complete bipartite graphs which matches a lower bound, valid for all bipartite graphs. We also show that determining f k ( G ) for an arbitrary graph G is NP-hard for every constant k > 1 . [ABSTRACT FROM AUTHOR]