Harper-type lower bounds and the bandwidths of the compositions of graphs (Q1381861)

Let \(G=(V,E)\) be a simple graph with order \(n\). A bijection \(f:V\to \{1,2, \dots, n\}\) is called a labeling of \(G\), and \(B(G,f)= \max_{uv\in E} | f(u) -f(v)|\) is the bandwidth of labeling \(f\). The bandwidth of \(G\) is the minimum bandwidth of the labelings of \(G\). The authors give a general Harper-type lower bound for the bandwidth of a graph. (This is a generalization of several known results.) By using this, they obtain a lower bound for the bandwidth of the composition of two graphs, and they also obtain the bandwidths of some composition graphs such as \((P_r \times P_s) [H]\), \((P_r \times C_s) [H]\) \((2r\neq s)\), etc., for any graph \(H\).