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