# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 3 Unary Graph Operations and Graph Transformations
### Line Graph  
In this subsection, we study the graph operation of creating a graph's line graph, using the notation formulated by [PERSON] and [PERSON] [49]. For a graph \(G\), its _line graph_, \(L(G)\), is defined by  
\[V(L(G)) =\{x_{\{u,v\}}\mid\{u,v\}\in E(G)\}\quad\text{and}\] \[E(L(G)) =\{\{x_{e},x_{f}\}\mid|\ e\cap f|=1\}.\]  
In other words, the line graph \(L(G)\) of a graph \(G\) has a vertex for every edge of \(G\), and two vertices of \(L(G)\) are adjacent if the corresponding edges in \(G\) are adjacent. The concept of a line graph, although not explicitly called a line graph, was first used by [PERSON] [27] in 1932. Furthermore, the underlying graph \(G\) of a given line graph \(L(G)\) is called the _root graph_ of \(L(G)\). Given a graph \(G\), it is possible to bound the tree-width (path-width) of its line graph in terms of the tree-width (path-width) of \(G\) and \(G\)'s maximum vertex degree. **Theorem 17**. : _For a graph \(G\), it holds that_  
\[ \begin{split} tw(G)-1&\leq tw(L(G))\leq(tw(G)+1) \Delta(G)-1\quad\text{and}\\ \frac{1}{2}(pw(G)+1)-1&\leq pw(L(G))\leq(pw(G)+1) \Delta(G)-1.\end{split} \]  
Proof. : The stated lower bound for the tree-width of \(L(G)\) was shown by [PERSON] and [PERSON] [50] in Proposition 2.3. A slightly weaker bound can be obtained as follows. Let \((\mathcal{X},T)\) be a tree-decomposition for \(L(G)\) of width \(\operatorname{tw}(L(G))\). In every bag of \((\mathcal{X},T)\), replace each edge of \(G\) with both of its endpoints. Then, we can obtain a tree-decomposition for \(G\) of width at most \(2(\operatorname{tw}(L(G))+1)-1\), such that \(\frac{1}{2}(\operatorname{tw}(G)+1)-1\leq\operatorname{tw}(L(G))\) follows. A similar argument results in the stated lower bound for path-width. The upper bounds are known from several works [51; 52; 53] and can be obtained as follows. Let \((\mathcal{X},T)\) be a tree-decomposition (\(\mathcal{X}\) a path-decomposition) for \(G\) of width \(\operatorname{tw}(G)\) (\(\operatorname{pw}(G)\)). If we replace every bag \(X_{u}\in\mathcal{X}\) with the set of all edges incident to at least one vertex in \(X_{u}\), we obtain a tree-decomposition (path-decomposition) for \(L(G)\) of width at most \((\operatorname{tw}(G)+1)\Delta(G)-1\) (\((\operatorname{pw}(G)+1)\Delta(G)-1\)). Stricter upper bounds than the ones shown in Theorem 17 can be found in Theorem 1.3 in the work by [PERSON] and [PERSON] [50]. Furthermore, it is easy to confirm that for every graph \(G\), the edges incident to a vertex of \(G\) with degree \(\Delta(G)\) form a clique of size \(\Delta(G)\) in \(L(G)\). With Lemmas 3 and 7, the following corollary follows immediately. **Corollary 5**. : _For a graph \(G\), it holds that \(tw(L(G))\geq\Delta(G)-1\) and \(pw(L(G))\geq\Delta(G)-1\)._  
For special graphs, the inequality turns into an equality, as the following result shows. **Proposition 8**. : _Let \(G\) be a graph. If \(tw(G)=1\) is true, it holds that \(tw(L(G))=\Delta(G)-1\). If \(pw(G)=1\) is true, it holds that \(pw(L(G))=\Delta(G)-1\)._  
The statement for tree-width was shown by [PERSON] and [PERSON] [50]. The statement for path-width follows from two arguments. For the lower bound, we refer to Corollary 5. For the upper bound, we know from Section 3.7 that a graph \(G\) of path-width one can be identified as a disjoint union of caterpillar graphs, allowing one to construct a path-decomposition of width at most \(\Delta(G)-1\) for \(L(G)\). In addition to providing a direct equation for how to obtain a line graph's tree-width (path-width) from its root graph's tree-width (path-width) if the root graph is a forest (caterpillar graph), the previous proposition shows that a line graph's tree-width (path-width) cannot be bounded in terms of its root graph's tree-width (path-width). We conclude this subsection with a theorem by [PERSON] and [PERSON] [54], showing how to derive a line graph's tree-width (path-width) from its root graph if the root graph is a complete graph. **Theorem 18**. : _For \(n\geq 2\), it holds that_  
\[tw(L(K_{n}))=pw(L(K_{n}))=