In graph theory, the graph bandwidth problem may be visualized as placing the vertices of a given graph at distinct integer positions along the number line so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement. It may be formalized as labeling the n {\displaystyle n} vertices v i {\displaystyle v_{i}} of a graph G {\displaystyle G} with distinct integers f ( v i ) {\displaystyle f(v_{i})} so that the quantity max { | f ( v i ) − f ( v j ) | : v i v j ∈ E } {\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}} is minimized, where E {\displaystyle E} is the edge set of G {\displaystyle G} . The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w i j {\displaystyle w_{ij}} and the cost function to be minimized is the product of weight with length, max { w i j | f ( v i ) − f ( v j ) | : v i v j ∈ E } {\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}} . In terms of matrices, the (unweighted) graph bandwidth is the minimal bandwidth of a symmetric matrix which is an adjacency matrix of the graph. The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size.
Bandwidth formulas for some graphs For several families of graphs, the bandwidth φ ( G ) {\displaystyle \varphi (G)} is given by an explicit formula. The bandwidth of a path graph P n {\displaystyle P_{n}} on n {\displaystyle n} vertices is 1, and the bandwidth of a complete graph K m {\displaystyle K_{m}} is φ ( K n ) = n − 1 {\displaystyle \varphi (K_{n})=n-1} . For the complete bipartite graph K m , n {\displaystyle K_{m,n}} ,
φ ( K m , n ) = ⌊ ( m − 1 ) / 2 ⌋ + n , {\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n,} assuming m ≥ n ≥ 1 {\displaystyle m\geq n\geq 1} . As a special case of this formula, the star graph S k = K k , 1 {\displaystyle S_{k}=K_{k,1}} on k + 1 {\displaystyle k+1} vertices has bandwidth φ ( S k ) = ⌊ ( k − 1 ) / 2 ⌋ + 1 {\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1} . For the hypercube graph Q n {\displaystyle Q_{n}} on 2 n {\displaystyle 2^{n}} vertices the bandwidth is
φ ( Q n ) = ∑ m = 0 n − 1 ( m ⌊ m / 2 ⌋ ) . {\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}
… excerpt ends here. Continue reading the full article.
