Sequences of radius k for complete bipartite graphs

Abstract: A emph{

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

.

Cites Work

Cited In (1)

   Recommendations

This page was built for publication: Sequences of radius $k$ for complete bipartite graphs