Bandwidth of the strong product of two connected graphs Original Research Article

The bandwidth image of a graph G is the minimum of the quantity image taken over all proper numberings f of G. The strong product of two graphs G and H, written as image, is the graph with vertex set image and with image adjacent to image if one of the following holds: (a) image and image are adjacent to image and image in G and H, respectively, (b) image is adjacent to image in G and image, or (c) image and image is adjacent to image in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by image. Let d be a positive integer and let image be two vertices of G. Let image denote the set of vertices image so that the distance between x and image in G is at most d. We define image as the minimum value of image over all vertices x of G. Let image denote the set of vertices z such that the distance between x and z in G is at most image and z is adjacent to y. We denote the larger of image and image by image. We define image if G is complete and image as the minimum of image over all pair of vertices image of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if image and image, then image. Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs.