**MSC:**- 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
- 68R10 Graph theory, See also {05Cxx, 90B10, 90B35, 90C35}

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$.