Let G and H be finite graphs, and suppose that H has at least as many vertices as G. The bandwidth of G with respect to H is defined by the author to be the minimum, over all injections p from the vertex set of G to that of H, of the maximum over all edges (u,v) of G of the distance in H between p(u) and p(v). The kth power of the graph H is the graph with the same vertex set as H, and vertices u,v are joined by an edge in the kth power if their distance in H is at most k. The author proves that the bandwidth of G with respect to H is the least k for which G can be embedded in the kth power of H.

The bandwidth of G with respect to H is shown to behave well with respect to increasing (or decreasing) graph parameters, where the latter are numerical functions of graphs that increase (or, respectively, decrease) in passing from subgraphs to graphs. Degree and chromatic number are examples of increasing parameters; diameter is an example of a decreasing parameter.

It follows from the result above that for any increasing (or, respectively, decreasing) graph parameter q, the bandwidth of G with respect to H is at least as large as the smallest k for which q(G) is less than or equal to (or, respectively, greater than or equal to) q applied to the kth power of H.

If G has n vertices and H is a path of length n, then the bandwidth of G with respect to H is the ordinary bandwidth of G; if H is a cycle of length n, then it is the cyclic bandwidth of G. By using the above minimum inequalities with various choices of graph parameters, the author obtains lower bounds for the bandwidth and cyclic bandwidth of G in terms of various distance and degree parameters of G.