Bandwidth of the strong product of two connected graphs

AbstractThe bandwidth B(G) of a graph G is the minimum of the quantity 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)H, is the graph with vertex set V(G)×V(H) and with (u1,v1) adjacent to (u2,v2) if one of the following holds: (a) u1 and v1 are adjacent to u2 and v2 in G and H, respectively, (b) u1 is adjacent to u2 in G and v1=v2, or (c) u1=u2 and v1 is adjacent to v2 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). Let d be a positive integer and let x,y be two vertices of G. Let NG(d)(x) denote the set of vertices v so that the distance between x and v in G is at most d. We define δ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-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 if G is complete and η(G) as the minimum of ηG(D(G))(x,y) over all pair of vertices x,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 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then 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