Bandwidth of the Cartesian product of two connected graphs (Q1613500): Difference between revisions

The authors investigate the bandwidth of the Cartesian product \(G\times H\) of two connected graphs \(G\) and \(H\) satisfying some order conditions. The bandwidth \(B(G)\) of a graph \(G=(V(G),E(G))\) is defined as the minimum of \(\{\max | f(u)-f(v)| :uv\in E(G)\}\) taken over all injective mappings \(f\) from \(V(G)\) to integers. Let \(G\) and \(H\) be connected graphs, let \(D(G)\) denote the diameter of \(G,\) let \(\kappa(H)\) denote the connectivity of \(H\) and let \(\varepsilon(G)=0\) if \(G\) is a complete graph with \(| V(G)| \geq 2\) and \(\varepsilon(G)=1\) if \(G\) is not complete. The main result of the paper is Theorem 1: Let \(G\) and \(H\) be connected graphs and let \(n\) be a positive integer. If \(n\leq\kappa(H)\) and \(| V(H)| \geq 2nD(G)-\varepsilon(G),\) then \(B(G\times H)\geq n| V(G)| .\) Corollaries for some classes of graphs are included.