Bandwidth of the Cartesian product of two connected graphs
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.
scientific article; zbMATH DE number 1792428