Konrad Engel, Sven Guttmann
Testing bandwidth $k$ for $k$-connected graphs
Preprint series:
Preprints aus dem Fachbereich Mathematik, Universität Rostock
- MSC:
- 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
- 68R10 Graph theory, See also {05Cxx, 90B10, 90B35, 90C35}
Abstract:
We present a linear-time algorithm to decide whether
a given $k$-connected graph has bandwidth k, where $k$
is a fixed positive integer. This improves the general
$O(n^{k+1})$-time-algorithm of Saxe for the recognition
of bandwidth-$k$ graphs on $n$ vertices under the special
supposition of connectivity $k$.
Keywords: bandwidth, bandwidth-$k$ graph, $k$-connected graph, linear-time algorithm