Bandwidth of the Composition of Certain Graph Powers

The composition of two graphs \(G\) and \(H\), written \(G[H]\), is the graph with vertex set \(V(G) \times V(H)\) and \((u_1,v_1)\) is adjacent to \((u_2,v_2)\) if \(u_1\) is adjacent to \(u_2\) in \(G\) or if \(u_1 = u_2\) and \(v_1\) is adjacent to \(v_2\) in \(H\). The \(r\)th power of graph \(G\), denoted \(G^r\), is the graph with vertex set \(V(G)\) and edge set \(\{(u,v) : d(u,v) \leq r \text{ in } G\}\). The bandwidth of graph \(G\) is \(\min \max |f(u) – f(v)|\), where the max is taken over each edge \(uv \in E(G)\), and the min is over all proper numberings \(f\). This paper establishes tight upper and lower bounds for the bandwidth of an arbitrary graph composition \(G[H]\), with the upper bound based only on \(|V(H)|\) and the bandwidth of \(G\). In addition, the exact bandwidth of the composition of \(G[H]\) is established for \(G\) the power of a path or a cycle.