Bandwidth for the Sum of \(k\) Graphs

The sum of a set of graphs \(G_1,G_2,\ldots,G_k\), denoted \(\sum_{k=1}^k G_i\), is defined to be the graph with vertex set \(V(G_1)\cup V(G_2)\cup…\cup V(G_k)\) and edge set \(E(G_1)\cup E(G_2)\cup…\cup E(G_k) \cup \{uw: u \in V(G_i), w \in V(G_j) for i \neq j\}\). In this paper, the bandwidth \(B\left(\sum_{k=1}^k G_i\right)\) for \(|V(G_i)| = n_i \geq n_{i+1}=|v(G_{i+1})|,(1 \leq i < k)\) with \(B(G_1) \leq {\lceil {n_1/2}\rceil} \) is established. Also, tight bounds are given for \(B\left(\sum_{k=1}^k G_i\right)\) in other cases. As consequences, the bandwidths for the sum of a set of cycles, a set of paths, and a set of trees are obtained.