Sequences of radius $k$ for complete bipartite graphs
Authors:
- Michał DębskiMDMichał Dębski
- Zbigniew LoncZLZbigniew Lonc
- Paweł RzążewskiPRPaweł Rzążewski
Preprint
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 $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$.
Keywords
All Related Versions
- Version 1, 2017-11-14, ArXiv
- Published version: Discrete Applied Mathematics, 225, 51.
This publication has 9 references indexed in Scilit:
- Achromatic and Harmonious Colorings of Circulant GraphsJournal of Graph Theory, 2017
- Constructing Optimal $k$-Radius SequencesSIAM Journal on Discrete Mathematics, 2016
- Sequences of large radiusEuropean Journal of Combinatorics, 2014
- Constructions of asymptotically shortest k-radius sequencesJournal of Combinatorial Theory, Series A, 2012
- The existence of k-radius sequencesJournal of Combinatorial Theory, Series A, 2012
- Universal cycles for minimum coverings of pairs by triples, with application to 2-radius sequencesMathematics of Computation, 2011
- Near Perfect Coverings in Graphs and HypergraphsEuropean Journal of Combinatorics, 1985
- The bandwidth problem for graphs and matrices—a surveyJournal of Graph Theory, 1982
- Complexity Results for Bandwidth MinimizationSIAM Journal on Applied Mathematics, 1978