# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 4 Binary Graph Operations
### [PERSON] and [PERSON] [74] introduced the corona of two graphs when they constructed a graph whose automorphism group is the wreath product of the two graphs' automorphism groups. The _corona_ of two vertex-disjoint graphs \(G_{1}\) and \(G_{2}\), denoted by \(G_{1}\wedge G_{2}\), consists of the disjoint union of one copy of \(G_{1}\) and \(|V(G_{1})|\) copies of \(G_{2}\), where each vertex of the copy of \(G_{1}\) is connected to all vertices of one copy of \(G_{2}\). In other words, \(|V(G_{1})||V(G_{2})|\) edges are inserted into the disjoint union of the \(|V(G_{1})|+1\) graphs.
\(X_{i+1}=V(K_{m}^{i})\cup\{v_{i},\ldots,v_{n}\}\) for \(\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}<i\leq n\). It is easy to check that \(\mathcal{X}\) satisfies all three requirements of a path-decomposition for \(K_{n}\wedge K_{m}\). Furthermore, we note that (a) \(\max_{1\leq i\leq\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}}|X_{i}|=m+\bigl{\lfloor} \frac{n}{2}\bigr{\rfloor}\), (b) \(|X_{\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}+1}|=n\), and (c) \(\max_{\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}<i\leq n}|X_{i+1}|=m+n-\bigl{\lfloor} \frac{n}{2}\bigr{\rfloor}\) hold. Next, let us differentiate two cases, \(m\leq\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}\) and \(m>\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}\):  
**Case 1: \(m\leq\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}\)**In this case, we have for (a) \(m+\left\lfloor\frac{n}{2}\right\rfloor\leq\left\lfloor\frac{n}{2}\right\rfloor+ \left\lfloor\frac{n}{2}\right\rfloor\leq n\) and for (c) \(m+\left(n-\left\lfloor\frac{n}{2}\right\rfloor\right)\leq\left\lfloor\frac{n}{2} \right\rfloor+n-\left\lfloor\frac{n}{2}\right\rfloor=n\), such that \(\max_{1\leq i\leq n+1}|X_{i}|=n\) holds. Thus, we know that the path-decomposition \(\mathcal{X}\) has a width of \(n-1\), yielding  
\[\max(n-1,m)=n-1\leq\mathrm{pw}(K_{n}\wedge K_{m})\leq n-1.\]  
Consequently, in this case, we obtain  
\[\mathrm{pw}(K_{n}\wedge K_{m})=n-1=n+\max\Bigl{(}0,m-\left\lfloor\frac{n}{2} \right\rfloor\Bigr{)}-1.\]  
**Case 2:**: \(m>\left\lfloor\frac{n}{2}\right\rfloor\)  
In this case, we have for (a) \(m+n-\left\lfloor\frac{n}{2}\right\rfloor=m+\left\lceil\frac{n}{2}\right\rceil \geq m+\left\lfloor\frac{n}{2}\right\rfloor\) and for (c) \(m+n-\left\lfloor\frac{n}{2}\right\rfloor=m+\left\lceil\frac{n}{2}\right\rceil \geq\left\lfloor\frac{n}{2}\right\rfloor+1+\left\lceil\frac{n}{2}\right\rceil =n+1\geq n\), such that \(\max_{1\leq i\leq n+1}|X_{i}|=m+n-\left\lfloor\frac{n}{2}\right\rfloor\) holds. Thus, the width of path-decomposition \(\mathcal{X}\) is \(m+n-\left\lfloor\frac{n}{2}\right\rfloor-1=n+\max(0,m-\left\lfloor\frac{n}{2} \right\rfloor)-1\), and it follows that  
\[\mathrm{pw}(K_{n}\wedge K_{m})\leq n+\max(0,m-\left\lfloor\frac{n}{2}\right\rfloor )-1\]  
holds. Lastly, we show that there cannot exist any path-decomposition \(\mathcal{X}^{\prime}\) for \(K_{n}\wedge K_{m}\) of width smaller than \(n+\max(0,m-\left\lfloor\frac{n}{2}\right\rfloor)-1\). To do so, let us assume that \(\mathcal{X}^{\prime}\) is a minimum path-decomposition for \(K_{n}\wedge K_{m}\) of the smallest possible width. As \(K_{n}\) is a subgraph of \(K_{n}\wedge K_{m}\), we know by Lemma 7 that there must exist at least one bag \(X\) in \(\mathcal{X}^{\prime}\) with \(V(K_{n})\subseteq X\). Furthermore, as \(K_{m+1}^{i}\) is a subgraph of \(K_{n}\wedge K_{m}\) for \(1\leq i\leq n\), we know by the same argument that there must exist at least one bag \(Y_{i}\) in \(\mathcal{X}^{\prime}\) with \(V(K_{m+1}^{i})\subseteq Y_{i}\) for every \(1\leq i\leq n\). Assuming that \(X\) and \(Y_{i},1\leq i\leq n\), contain no more than the previously mentioned sets of vertices, \(V(K_{n}\wedge K_{m})=X\cup\cup_{i=1}^{n}Y_{i}\) is true, and for every edge \(\{u,v\}\in E(K_{n}\wedge K_{m})\), it holds that \(u,v\in X\) if \(u,v\in V(K_{n})\) or \(u,v\in Y_{i}\) if \(u,v\in V(K_{m+1}^{i})\). Consequently, the bags \(X,Y_{1},\ldots,Y_{n}\) satisfy (pw-1) and (pw-2). Furthermore, note that every \(u_{j}^{i}\in V(K_{m}^{i})\), \(1\leq j\leq m\), \(1\leq i\leq n\), satisfies \(N_{K_{n}\wedge K_{m}}(u_{j}^{i})\subseteq Y_{i}\), such that \(u_{j}^{i}\) only needs to be part of bag \(Y_{i}\) and would violate the assumption of \(\mathcal{X}^{\prime}\) being minimal. As every \(v_{i}\), \(1\leq i\leq n\), is part of \(X\) and exactly one other bag, namely \(Y_{i}\), no ordering of the bags \(X,Y_{1},\ldots,Y_{n}\) can satisfy (pw-3).