A structural characterization and a new linear-time algorithm for the recognition of bandwidth-2 graphs
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock
MSC:
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
90C35 Programming involving graphs or networks
Abstract: Bandwidth--2 graphs are simple graphs $G=(V,E)$ which are not a disjoint

union of paths and for which there is a bijective mapping $f: V \rightarrow \{1,\ldots,|V|\}$ such that $\max\{|f(v)-f(u)|: vw \in E\}= 2$.

Results on the structure of such graphs are presented. The corresponding

properties lead to the definition of weak bandwidth--2 graphs. This more

general class can be recognized by a modification of the well--known

DFS--algorithm for the construction of the block--cutvertex graph. In this

larger class the bandwidth--2 graphs can be filtered out by a simple

procedure on the blocks and a greedy procedure which locally depends on

several cases given by the position and the length of the hairs.

Altogether, a new linear--time algorithm for the recognition of bw--2

graphs is given.

Keywords: bandwidth, bandwidth-2 graph, graph recognition, block-cutvertex graph, pentadiagonal matrix