Bandwidth for the Sum of $k$ Graphs

Abstract

The sum of a set of graphs $G_1,G_2,\dots ,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 \dots \cup V(G_k)$ and edge set $E(G_1)\cup E(G_2)\cup \dots \cup E(G_k)\cup \{uw:u\in V(G_i),w\in V(G_j)fori\ne j\}$. In this paper, the bandwidth $B\left(\sum _{k=1}^k{G}_i\right)$ for $|V(G_i)|=n_i\ge n_{i+1}=|v(G_{i+1})|,(1\le i<k)$ with $B(G_1)\le \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.