Bounding the bandwidths for graphs

Abstract

Let 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πmaxuν∈E(G) dH(π(u), π(ν)), 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 ..