Bandwidth of the strong product of two connected graphs (Q2470005)

The bandwidth \(B(G)\) of an undirected graph \(G\) is the minimum over all proper vertex-numberings of the graph of the maximum absolute number difference of endpoints of all edges. The strong product \(G(Sp)H\) of two graphs \(G\) and \(H\) is obtained on the product of their vertex sets by connecting those pairs that are pairwise connected or equal. The formula \[ B(G(Sp)H)=B(G)| V(H)| +B(H) \] is shown to hold under particular conditions, allowing to derive the bandwidth of strong products of powers of paths with complete bipartite graphs.