Bounding the bandwidths for graphs (Q1583541)

Let \(G,H\) be finite graphs with \(|V(H)|\geqslant|V(G)|\). The bandwidth of \(G\) with respect to \(H\) is defined to be \(B_H(G)=\min_{\pi} \max_{uv\in E(G)} d_H(\pi(u),\pi(v))\), with the minimum taken over all injections \(\pi\) from \(V(G)\) to \(V(H),\) where \(d_{H}(x,y)\) is the distance in \(H\) between two vertices \(x,y \in V(H)\). This number is involved with the VLSI design and optimization, especially when the ``host'' graph \(H\) is a path \(P_{n}\) or a cycle \(C_{n}\) of length \(n=|V(G)|\). In these two cases, \(B_{H}(G)\) is known to be the ordinary bandwidth \(B(G)\) and the cyclic bandwidth \(B_{c}(G),\) respectively, and the corresponding decision problem is NP-complete. So estimations of \(B(G),\) \(B_{c}(G)\) and in general \(B_{H}(G)\) are needed, especially in determining the bandwidths of some specific graphs. We first propose a systematic method for obtaining lower bounds for the bandwidth \(B_{H}(G).\) By using this method, we then get a number of lower bounds for \(B(G)\) and \(B_{c}(G)\) in terms of some distance- and degree-related parameters.