| Autor: |
Dębski, Michał, Lonc, Zbigniew, Rzążewski, Paweł |
| Rok vydání: |
2017 |
| Předmět: |
|
| Zdroj: |
Discrete Applied Mathematics 225, pp. 51--63. 2017 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1016/j.dam.2017.03.017 |
| Popis: |
A \emph{$k$-radius sequence} for a graph $G$ is a sequence of vertices of $G$ (typically with repetitions) such that for every edge $uv$ 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$. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
