# 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. Alternatively, the corona of \(G_{1}\) and \(G_{2}\) can also be obtained by applying 1-sum and dominating vertex operations as follows. Let \(V(G_{1})=\{v_{1},\ldots,v_{n}\}\) be the vertex set of \(G_{1}\). For \(i=1,\ldots,n\), we take a copy of \(G_{2}\), insert a dominating vertex \(w_{i}\) (cf. Section 3.1) into that copy, and obtain the resulting graph \(G_{2,j}\). Then, the following sequence of 1-sums,  
\[(\ldots((G_{1}\oplus_{v_{1},v_{1}}G_{2,1})\oplus_{v_{2},v_{2}}G_{2,2})\ldots) \oplus_{v_{n},v_{n}}G_{2,n}, \tag{1}\]  
results in the corona \(G_{1}\wedge G_{2}\) of \(G_{1}\) and \(G_{2}\). With this observation, we can bound the tree-width (path-width) of \(G_{1}\wedge G_{2}\) in the tree-width (path-width) of its combined graphs as follows. Theorem 4.2: _Let \(G_{1}\) and \(G_{2}\) be two vertex-disjoint graphs. Then, it holds that_  
\[\max(tw(G_{1}),tw(G_{2})) \leq tw(G_{1}\wedge G_{2})\leq\max(tw(G_{1}),tw(G_{2}))+1\quad \text{and}\] \[\max(pw(G_{1}),pw(G_{2})) \leq pw(G_{1}\wedge G_{2})\leq\max(pw(G_{1}),pw(G_{2}))+|V(G_{1})|.\]  
Proof. : The lower bounds follow from Corollary 2 since \(G_{1}\) and \(G_{2}\) are subgraphs of \(G_{1}\wedge G_{2}\). For the upper bounds, we make use of our earlier observation that we can obtain the corona of \(G_{1}\) and \(G_{2}\) by applying 1-sum and dominating vertex operations as described in Equation (1). By Theorem 3, it follows that \(\operatorname{tw}(G_{2,i})\leq\operatorname{tw}(G_{2})+1\) and \(\operatorname{pw}(G_{2,i})\leq\operatorname{pw}(G_{2})+1\). By Theorem 4.2 and Equation (1), it follows that \(\operatorname{tw}(G_{1}\wedge G_{2})\leq\max(\operatorname{tw}(G_{1}), \operatorname{tw}(G_{2}))+1\) and \(\operatorname{pw}(G_{1}\wedge G_{2})\leq\max(\operatorname{pw}(G_{1}), \operatorname{pw}(G_{2}))+|V(G_{1})|\). With the previous theorem proved, we ask ourselves whether there exists a constant integer \(c\in\mathbb{N}\), such that for all graphs \(G_{1},G_{2}\), it holds that \(\operatorname{pw}(G_{1}\wedge G_{2})\leq\max(\operatorname{pw}(G_{1}), \operatorname{pw}(G_{2}))+c\), similar to the upper bound for tree-width. The following proposition provides a negative answer to this question. Proposition 10: _For \(n\geq 2\) and \(m\geq 1\), it holds that_  
\[pw(K_{n}\wedge K_{m})=n+\max\Bigl{(}0,m-\Bigl{\lfloor}\frac{n}{2}\Bigr{\rfloor} \Bigr{)}-1.\]  
Proof. : We write \(K_{n}=(\{v_{1},\ldots,v_{n}\},\{v_{i},v_{j}\}\mid 1\leq i<j\leq n\})\) and \(K_{m}=(\{u_{1},\ldots,u_{m}\},\{\{u_{i},u_{j}\}\mid 1\leq i<j\leq m\})\). For \(1\leq i\leq n\), we denote the \(n\) copies of \(K_{m}\) in \(K_{n}\wedge K_{m}\) as \(K_{m}^{i}\) with \(V(K_{m}^{i})=\{u_{1}^{i},\ldots,u_{m}^{i}\}\). By construction of \(K_{n}\wedge K_{m}\), every vertex \(v_{i}\) of \(K_{n}\) gets connected to all vertices of \(K_{m}^{i}\), resulting in \(n\) cliques of size \(m+1\), which we denote by \(K_{m+1}^{i}\) with \(V(K_{m+1}^{i})=V(K_{m}^{i})\cup\{v_{i}\}\) for \(1\leq i\leq n\). Since \(K_{m+1}^{i}\), \(1\leq i\leq n\), and \(K_{n}\) are subgraphs of \(K_{n}\wedge K_{m}\), it follows from Corollary 2 that \(\max(n-1,m)\leq\operatorname{pw}(K_{n}\wedge K_{m})\) must hold. Next, let us construct the following path-decomposition \(\mathcal{X}=(X_{1},\ldots,X_{n+1})\) for \(K_{n}\wedge K_{m}\). We define the following:  
1. \(X_{i}=V(K_{m}^{i})\cup\{v_{1},\ldots,v_{i}\}\) for \(1\leq i\leq\bigl{\lfloor}\frac{n}{2}\bigr{\rfloor}\);
2. \(X_{\lfloor\frac{n}{2}\rfloor+1}=V(K_{n})\);
3.