Konrad Engel, Sven Guttmann
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.)
- 68R10 Graph theory, See also {05Cxx, 90B10, 90B35, 90C35}
- 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