# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 3 Unary Graph Operations and Graph Transformations
### Power of a Graph  
For \(d\in\mathbb{N}\) and a graph \(G\), we denote the _\(d\)-th power_ of \(G\) by \(G^{d}\). Thus, \(G^{d}\) has the same set of vertices as \(G\), i.e., \(V(G^{d})=V(G)\), and two vertices of \(G^{d}\) are adjacent if and only if there exists a path of length at most \(d\) in \(G\) between these vertices. To begin, the following lemma provides an upper bound on the number of neighbors each vertex might have in the \(d\)-th power of a graph \(G\). **Lemma 9**: _Given \(d\in\mathbb{N}\) and a graph \(G\), for every vertex \(v\in V(G)\), it holds that_  
\[\deg_{G^{d}}(v)\leq\Delta(G)\sum_{i=0}^{d-1}(\Delta(G)-1)^{i}.\]  
Proof. : Let \(v\in V(G)\) be a vertex of \(G\). To obtain an upper bound on the number of neighbors \(v\) might have in \(G^{d}\), we derive an upper bound for the number of vertices reachable from \(v\) within a distance of at most \(d\) in \(G\). By definition, we know that \(\deg_{G}(v)\leq\Delta(G)\) holds, such that \(v\) has at most \(\Delta(G)\) neighbors in \(G\). By the same argument, every neighbor \(u\) of \(v\) in \(G\) has at most \(\Delta(G)\) neighbors. However, one of those neighbors of \(u\) is \(v\), such that \(u\) has at most \(\Delta(G)-1\) not-yet-considered neighbors. Repeating the previous argument \(d-1\) times, we obtain an upper bound on the number of vertices at an exact distance \(d\) to \(v\),  
\[\Delta(G)(\Delta(G)-1)^{d-1}.\]  
Since we are interested in an upper bound on the number of vertices with a distance of _at most_\(d\) to \(v\), we need to sum up the upper bounds for all intermediate distances from one up to \(d\). By doing so, we obtain  
\[\Delta(G)+\Delta(G)(\Delta(G)-1)+\ldots+\Delta(G)(\Delta(G)-1)^{d-1}=\Delta(G) \sum_{i=0}^{d-1}(\Delta(G)-1)^{i}.\]  
As every vertex that is reachable from \(v\) in \(G\) within a distance of at most \(d\) is adjacent to \(v\) in \(G^{d}\), it follows that  
\[\deg_{G^{d}}(v)\leq\Delta(G)\sum_{i=0}^{d-1}(\Delta(G)-1)^{i}\]  
holds. Note that the previously stated upper bound is tight. To see this, consider a tree \(T\) with root \(v\in V(T)\) and three binary subtrees of equal but arbitrary depth adjacent to \(v\). The following theorem makes use of this upper bound for a vertex's number of neighbors in the \(d\)-th power of a graph to study the effect of raising a graph to the power of \(d\) with respect to tree-width and path-width. **Theorem 16**: _For \(d\in\mathbb{N}\) and a graph \(G\), it holds that_  
\[tw(G) \leq tw(G^{d})\leq(tw(G)+1)\Bigg{(}1+\Delta(G)\sum_{i=0}^{d-1}( \Delta(G)-1)^{i}\Bigg{)}-1\quad\text{and}\] \[pw(G) \leq pw(G^{d})\leq(pw(G)+1)\Bigg{(}1+\Delta(G)\sum_{i=0}^{d-1}( \Delta(G)-1)^{i}\Bigg{)}-1.\]  
Proof. : The lower bounds follow from Corollary 2, as \(G\) is a subgraph of \(G^{d}\). For the upper bounds, denote by \((\mathcal{X},T)\) a tree-decomposition (by \(\mathcal{X}\) a path-decomposition) of \(G\). By constructing \(G^{d}\), we know all neighbors of every vertex \(v\in V(G)\) in \(G^{d}\). To obtain a tree-decomposition (path-decomposition) for \(G^{d}\), for every vertex \(v\in V(G)\), we add all neighbors of \(v\) in \(G^{d}\), i.e., \(N_{G^{d}}(v)\), to every bag \(X\in\mathcal{X}\) containing \(v\). We denote the resulting bag by \(X^{\prime}\) and the resulting set of bags by \(\mathcal{X}^{\prime}\). Then, by Lemma 9, every bag of \(\mathcal{X}^{\prime}\) contains at most\[(\text{tw}(G)+1)\Bigg{(}1+\Delta(G)\sum_{i=0}^{d-1}(\Delta(G)-1)^{i} \Bigg{)}\] \[\Bigg{(}(\text{pw}(G)+1)\Bigg{(}1+\Delta(G)\sum_{i=0}^{d-1}(\Delta( G)-1)^{i}\Bigg{)}\Bigg{)}\]  
vertices. Taking \(G\) to the power of \(d\) does not alter the set of vertices, i.e., \(V(G)=V(G^{d})\), such that \((\mathcal{X}^{\prime},T)\) (\(\mathcal{X}^{\prime}\)) still satisfies (tw-1) ((pw-1)). By adding, for every vertex \(v\in V(G)\), all neighbors of \(v\) in \(G^{d}\) to every bag containing \(v\), all new edges introduced into \(G^{d}\) are covered, such that \((\mathcal{X}^{\prime},T)\) (\(\mathcal{X}^{\prime}\)) satisfies (tw-2) ((pw-2)).