# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 4 Binary Graph Operations
### Graph Product  
The graph product of two vertex-disjoint graphs \(G_{1}\) and \(G_{2}\) is a new graph with vertex set \(V(G_{1})\times V(G_{2})\) and an edge set derived from the adjacency, equality, or non-adjacency of vertices in the original graphs \(G_{1}\) and \(G_{2}\). In this work, we consider the Cartesian [65], categorical [66], co-normal [67], lexicographic [68], and normal [65] graph products, as well as the symmetric difference [67] and the rejection [67]. [PERSON] introduced the categorical graph product as the \"Kronecker product\", while [PERSON] and [PERSON] referred to it as the \"conjunction\". The normal graph product was introduced by [PERSON] as the \"strong product\". The co-normal graph product was introduced by [PERSON] and [PERSON] as the \"disjunction\", and the lexicographic graph product was initially defined by [PERSON] as the \"composition\". All graph products, their respective notations, and the edge sets of the resulting graphs are listed in Table 1. For more exhaustive definitions and in-depth results on these graph products, we refer to the works by [PERSON] and [PERSON] [69] and [PERSON] and [PERSON] [70]. Besides these graph products, [PERSON] and [PERSON] defined the \(\gamma\)-product of two graphs \(G_{1}\) and \(G_{2}\) as \(\overline{\overline{G_{1}}\vee\overline{G_{2}}}\)[71]. By transforming the edge set of the \(\gamma\)-product of two graphs \(G_{1}\) and \(G_{2}\), it follows that \(\overline{\overline{G_{1}}\vee\overline{G_{2}}}=G_{1}\star G_{2}\) holds. In other words, the \(\gamma\)-product is merely a different formulation for the normal product of two graphs. Furthermore, by transforming the edge set of \(G_{1}|G_{2}\), we obtain \(G_{1}|G_{2}=\overline{G_{1}}\star\overline{G_{2}}\), while transforming the edge set of \(G_{1}\triangle G_{2}\) results in \(G_{1}\triangle G_{2}=(G_{1}\times G_{2})\cup(G_{1}\star_{\text{cat}}\overline {G_{2}})\cup(\overline{G_{1}}\star_{\text{cat}}G_{2})\). For two paths \(P_{n}\), \(P_{m}\) with \(n,m\in\mathbb{N}\), it holds that \(P_{n}\times P_{m}\) is an \(n\times m\)-grid graph. Consequently, for two graphs \(G_{1}\) and \(G_{2}\), it is generally not possible to bound the tree-width (path-width) of \(G_{1}\times G_{2}\) from above by the tree-widths (path-widths) of \(G_{1}\) and \(G_{2}\) (cf. Example 4). With \(P_{n}\times P_{m}\) being a subgraph of \(P_{n}\lor P_{m}\), \(P_{n}\star P_{m}\), and \(P_{n}\triangle P_{m}\), the same result follows from Corollary 2 for the co-normal and normal graph products, as well as the symmetric difference. Next, \(P_{n}\star_{\text{cat}}P_{m}\) has an \(a\times a\)-grid graph, with \(a\) proportional to \(\min(n,m)\) as a subgraph, so that by the same argument as before, the tree-width (path-width) of \(G_{1}\star_{\text{cat}}G_{2}\) can generally not be bound from above by the tree-widths  
\begin{table}
\begin{tabular}{l l l} \hline \hline
**Graph Product** & **Notation** & **Edge Set \(\{\{(u_{1}u_{2}),(v_{1},v_{2})\}\}\)** \\ \hline Cartesian & \(G_{1}\times G_{2}\) & \((u_{1}=v_{1}\wedge\{u_{2},v_{2}\}\in E(G_{2}))\) \\  & \(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\(path-widths) of \(G_{1}\) and \(G_{2}\). For \(n,m\in\mathbb{N}\), let \(I_{n}\) and \(I_{m}\) denote the graphs that contain \(n\) and \(m\) isolated vertices. From our earlier observation, we know that \(I_{n}|I_{m}=K_{n}\star K_{m}\) holds. Consequently, the tree-width (path-width) of \(I_{n}|I_{m}\) cannot be bound from above by the tree-widths (path-widths) of \(I_{n}\) and \(I_{m}\), as \(\operatorname{tw}(I_{n})=\operatorname{pw}(I_{n})=1\) holds, while \(K_{n}\) and \(K_{m}\) are subgraphs of \(I_{n}|I_{m}\), such that by Lemma 3 (Lemma 7), \(\operatorname{tw}(I_{n}|I_{m})\geq\max(n,m)-1\) (\(\operatorname{pw}(I_{n}|I_{m})\geq\max(n,m)-1\)) follows.