Bounding the bandwidths for graphs

AbstractLet G,H be finite graphs with |V(H)|⩾|V(G)|. The bandwidth of G with respect to H is defined to be BH(G)=minπmaxuv∈E(G)dH(π(u),π(v)), with the minimum taken over all injections π from V(G) to V(H), where dH(x,y) is the distance in H between two vertices x,y∈V(H). This number is involved with the VLSI design and optimization, especially when the “host” graph H is a path Pn or a cycle Cn of length n=|V(G)|. In these two cases, BH(G) is known to be the ordinary bandwidth B(G) and the cyclic bandwidth Bc(G), respectively, and the corresponding decision problem is NP-complete. So estimations of B(G), Bc(G) and in general BH(G) are needed, especially in determining the bandwidths of some specific graphs. In this paper, we first propose a systematic method for obtaining lower bounds for the bandwidth BH(G). By using this method, we then get a number of lower bounds for B(G) and Bc(G) in terms of some distance- and degree-related parameters