# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 5 Conclusions and Outlook  
In Section 3, we showed how the tree-width or path-width of a given graph changes if we apply a certain, unary graph transformation \(f\) to this graph. In all cases in which it is possible to bound the tree-width or path-width of the resulting graph \(f(G)\), we also showed how to compute the corresponding decomposition in time linear in the size of the decomposition for \(G\). Table 2 summarizes the results. It is noteworthy that the behavior of tree-width and path-width under the considered transformations is almost identical. Furthermore, in Section 4, we considered various binary graph operations \(f\), creating a new graph \(f(G_{1},G_{2})\) out of two graphs \(G_{1}\) and \(G_{2}\). In all cases in which it is possible to bound the tree-width or path-width of the combined graph \(f(G_{1},G_{2})\) in terms of the tree-width or path-width of \(G_{1}\) and \(G_{2}\), we showed how to compute the corresponding decomposition in time linear in the size of the decompositions for \(G_{1}\) and \(G_{2}\), such that our results are constructive. In Table 3, we summarize these results, which show that, with the exception of the corona of two graphs, the behavior of tree-width and path-width under the considered operations is nearly identical. The results in Sections 3.2 and 3.3 allow for generalizing known results on the stability of trees and forests [75; 76] to the stability of graph classes of bounded tree-width [77]. \begin{table}
\begin{tabular}{l l l} \hline \hline
**Transformation \(f\)** & \(\mathbf{tw}(f(G))\) & \(\mathbf{pw}(f(G))\) \\ \hline Vertex deletion & \(k\) & \(k\) \\ Vertex addition & \(k+1\) & \(k+1\) \\ Edge deletion & \(k\) & \(k\) \\ Edge addition & \(k+1\) & \(k+1\) \\ Subgraph & \(k\) & \(k\) \\ Vertex identification & \(k+1\) & \(k+1\) \\ Edge contraction & \(k\) & \(k\) \\ Edge subdivision & \(k\) & \(k+1\) \\ Minor & \(k\) & \(k\) \\ Switching & \(k+1\) & \(k+1\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Let \(G\) be a graph of tree-width (path-width) \(k\), and let \(f\) be the unary graph transformation in the first column. The second column lists the upper bound for the tree-width, and the third column lists the upper bound for the path-width of \(f(G)\). \begin{table}
\begin{tabular}{l l l} \hline \hline
**Operation \(f\)** & \(\mathbf{tw}(f(G_{1},G_{2}))\) & \(\mathbf{pw}(f(G_{1},G_{2}))\) \\ \hline Disjoint union & \(\max(k_{1},k_{2})\) & \(\max(k_{1},k_{2})\) \\ Join & \(\min(k_{1}+n_{2},k_{2}+n_{1})\) & \(\min(k_{1}+n_{2},k_{2}+n_{1})\) \\ Substitution & \(\min(k_{1}+n_{2},k_{2}+n_{1})-1\) & \(\min(k_{1}+n_{2},k_{2}+n_{1})-1\) \\ Lexicographic product & \((k_{1}+1)n_{2}-1\) & \((k_{1}+1)n_{2}-1\) \\
1-sum & \(\max(k_{1},k_{2})\) & \(\max(k_{1},k_{2})+1\) \\ Corona & \(\max(k_{1},k_{2})+1\) & \(\max(k_{1},k_{2})+n_{1}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Let \(G_{1}\) and \(G_{2}\) be two graphs of tree-width (path-width) \(k_{1}\) and \(k_{2}\), respectively, and let \(f\) be the binary graph operation from the first column. Let \(n_{1}\) denote the number of vertices of \(G_{1}\) and \(n_{2}\) the number of vertices of \(G_{2}\). The second column lists the upper bound for the tree-width, and the third column lists the upper bound for the path-width of the graph \(f(G_{1},G_{2})\). Most of our results provide tight upper and lower bounds for the tree-width and path-width of the resulting graph in terms of those of the initial graphs or argue why such bounds are impossible. For the remaining case, it has yet to be shown whether our bounds are the best possible or whether stricter bounds can be provided. The bounds for the tree-width and path-width of the power of a graph, as shown in Section 3.8, are very rough, as all vertex degrees are approximated by the maximum degree of the graph. Furthermore, we did not provide lower bounds for the tree-width (path-width) of the categorical or co-normal graph product of two graphs, nor for the symmetric difference or rejection of two graphs.