Harper-type lower bounds and the bandwidths of the compositions of graphs

Abstract

We give a general Harper-type lower bound for the bandwidth of a graph which is a common generalization of several known results. As applications we get a lower bound for the bandwidth of the composition of two graphs. By using this we determine the bandwidths of some composition graphs such as (Pr × Ps)[H], (Pr × Cs)[H] (2r ≠ s), (Cr × Cs)[H] (6 ≤ 2r ≤ s), etc., for any graph H. Interestingly, the bandwidths of these graphs have nothing to do with the structure of H in general.