Bandwidth of the strong product of two connected graphs

The bandwidth B(G)B(G) of a graph G   is the minimum of the quantity max{|f(x)-f(y)|:xy∈E(G)}max{|f(x)-f(y)|:xy∈E(G)} taken over all proper numberings f of G. The strong product of two graphs G and H  , written as G(SP)HG(SP)H, is the graph with vertex set V(G)×V(H)V(G)×V(H) and with (u1,v1)(u1,v1) adjacent to (u2,v2)(u2,v2) if one of the following holds: (a) u1u1 and v1v1 are adjacent to u2u2 and v2v2 in G and H  , respectively, (b) u1u1 is adjacent to u2u2 in G   and v1=v2v1=v2, or (c) u1=u2u1=u2 and v1v1 is adjacent to v2v2 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 D(G)D(G). Let d   be a positive integer and let x,yx,y be two vertices of G  . Let NG(d)(x) denote the set of vertices vv so that the distance between x   and vv in G is at most d  . We define δd(G)δd(G) as the minimum value of |NG(d)(x)| over all vertices x of G  . Let NG(d)(x,y) denote the set of vertices z such that the distance between x and z in G   is at most d-1d-1 and z is adjacent to y  . We denote the larger of |NG(d)(x,y)| and |NG(d)(y,x)| by ηG(d)(x,y). We define η(G)=1η(G)=1 if G   is complete and η(G)η(G) as the minimum of ηG(D(G))(x,y) over all pair of vertices x,yx,y of G otherwise. Let G and H   be two connected graphs. Among other results, we prove that if δD(H)(G)⩾B(G)D(H)+1δD(H)(G)⩾B(G)D(H)+1 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then B(G(SP)H)=B(G)|V(H)|+B(H)B(G(SP)H)=B(G)|V(H)|+B(H). 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.