Title: Bandwidth of the strong product of two connected graphs
Abstract: The 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 ( S P ) H , is the graph with vertex set V ( G ) × V ( H ) and with ( u 1 , v 1 ) adjacent to ( u 2 , v 2 ) if one of the following holds: (a) u 1 and v 1 are adjacent to u 2 and v 2 in G and H , respectively, (b) u 1 is adjacent to u 2 in G and v 1 = v 2 , or (c) u 1 = u 2 and v 1 is adjacent to v 2 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 N G ( 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 | N G ( d ) ( x ) | over all vertices x of G . Let N G ( 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 | N G ( d ) ( x , y ) | and | N G ( 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 ( S P ) 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.