Bandbreite, Kenngröße eines Graphen.

Ist G numerierter Graph der Ordnung n, so nennt man

\begin{eqnarray}B(G)=\,\min \{{B}_{f}(G):f\,{\rm{Numerierung}}\,{\rm{von}}\,G\}\end{eqnarray} seine Bandweite. Dabei bedeutet f : ∈ (G) → {1, 2, …, n} eine bijektive Abbildung, also eine Numerierung von G und \begin{eqnarray}{B}_{f}(G)=\,{\rm{\max }}\{|f(u)-f\,(v)|:\,uv\in K(G)\}\end{eqnarray} die Bandweite oder Bandbreite von f.

Für einfache Graphen kann man die Bandweite mühelos bestimmen. Ist z. B. W ein Weg und C ein Kreis, so gilt B(W) = 1 und B(C) = 2. Natürlich gilt B(K_n) = n − 1 für den vollständigen Graphen K_n, und man berechnet \begin{eqnarray}B({K}_{p,q})=p+\lceil q/2\rceil -1\end{eqnarray}für den vollständigen bipartiten Graphen K_p,q, falls p ≤ q gilt. Das allgemeine Bandweitenproblem ist allerdings ein beweisbar schwieriges, ein NP-vollständiges Problem.