Bandwidth of the cartesian product of two connected graphs

摘要

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 injective integer numberings f of G. The cartesian product of two graphs G and H, written as G * H, is the graph with vertex set V(G) * V(H) and with (u_1, v_1) adjacent to (u_2, v_2) if either u_1 is adjacent to u_2 in G and v_1 = v_2 or u_1 = u_2 and v_1 is adjacent to v_2. In this paper we investigate the bandwidth of the cartesian product of two connected graphs. For a graph G, we denote the diameter of G and the connectivity of G by D(G) and k(G), respectively. Let G and H be two connected graphs. Among other results, we show that if B(H) = k(H) and |V(H)| ≥ 2B(H)D(G) - min{1, D(G) - 1}, then B(G * H) = B(H)|V(G)|. Moreover, the order condition in this result is sharp.