Sequences of radius kk for complete bipartite graphs

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