# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 3 Unary Graph Operations and Graph Transformations
### Seidel Switching  
The Seidel switching operation was introduced by the Dutch mathematician [PERSON] in connection with regular structures, such as systems of equiangular lines, strongly regular graphs, or so-called two-graphs [57; 58; 59]. Several examples of applications of Seidel switching can be found in algorithms, e.g., in a polynomial-time algorithm for the \(P_{3}\)-structure recognition problem [60] or in an algorithm for the construction of bi-join decompositions of graphs [61]. For a graph \(G\) and a vertex \(v\in V(G)\), the graph resulting from a _Seidel switching_ operation, denoted by \(S(G,v)\), is defined as follows. The vertex set of \(S(G,v)\) is the same as the vertex set of \(G\), i.e., \(V(S(G,v))=V(G)\), and the edge set of \(S(G,v)\) is defined as  
\[E(S(G,v))=E(G) \setminus\{\{v,w\}\mid w\in N_{G}(v)\}\] \[\cup\{\{v,w\}\mid w\in V(G)\setminus(N_{G}(v)\cup\{v\})\}.\]  
In other words, every neighbor of \(v\) in \(G\) is a non-neighbor of \(v\) in \(S(G,v)\), and every non-neighbor of \(v\) in \(G\) is a neighbor of \(v\) in \(S(G,v)\). Given this definition of Seidel switching, by extending a result by [PERSON] and [PERSON] [62], we show that a single Seidel switching operation increases or decreases a graph's tree-width and path-width by at most one. **Theorem 20**: _For a graph \(G\) and a vertex \(v\in V(G)\), it holds that_  
\[tw(G)-1\leq tw(S(G,v))\leq tw(G)+1\quad\text{and}\] \[pw(G)-1\leq pw(S(G,v))\leq pw(G)+1.\]  
For the upper bounds, let \((\mathcal{X},T)\) be a tree-decomposition (\(\mathcal{X}\) a path-decomposition) for \(G\) of width \(\operatorname{tw}(G)\) (\(\operatorname{pw}(G)\)). When we add \(v\) to all bags of \(\mathcal{X}\), denoting the resulting set of bags by \(\mathcal{X}^{\prime}\), we obtain a tree-decomposition \((\mathcal{X}^{\prime},T)\) (a path-decomposition \(\mathcal{X}^{\prime}\)) for \(S(G,v)\) of width at most \(\operatorname{tw}(G)+1\) (\(\operatorname{pw}(G)+1\)). Consequently, \(\operatorname{tw}(S(G,v))\leq\operatorname{tw}(G)+1\) (\(\operatorname{pw}(S(G,v))\leq\operatorname{pw}(G)+1\)) follows. Since \(S(S(G,v),v)=G\) holds, we can derive the lower bound from the upper bound via \(\operatorname{tw}(G)=\operatorname{tw}(S(S(G,v),v)\leq\operatorname{tw}(S(G,v ))+1\) (\(\operatorname{pw}(G)=\operatorname{pw}(S(S(G,v),v))\leq\operatorname{pw}(S(G, v))+1\)). Note that the bounds shown in Theorem 20 are tight. To convince oneself of this fact, consider the path with four vertices, \(P_{4}\). Its tree-width and path-width are one. Denote by \(v\) one of the two vertices in \(P_{4}\) with degree one. Then, \(S(P_{4},v)\) contains \(K_{3}\) as a minor, such that a tree-width and path-width of at least two follow. Following the example in the opposite direction, i.e., applying the Seidel switching operation to \(S(P_{4},v)\) for the same vertex \(v\) provides an example that the lower bound is also tight. In 1980, [PERSON] and [PERSON] [63] studied the complexity of the decision problem of whether two graphs are switching equivalent. In their work, they proved that this decision problem is polynomial-time equivalent to the decision problem of graph isomorphism. Thus, two graphs \(G\) and \(G^{\prime}\) with the same vertex set \(V\) are called _switching equivalent_ if there exists a sequence of vertices \((v_{1},\ldots,v_{\ell})\) in \(V\), such that for \(G^{0}=G\) and \(G^{i}=S(G^{i-1},v_{i})\), \(1\leq i\leq\ell\), it holds that \(G^{\ell}=G^{\prime}\). In 2012, [PERSON] and [PERSON] [62] considered in their work the tree-width of switching classes. By the definition of switching equivalence and via Theorem 20, we can formulate the following corollary, contributing to the research on the tree-width of switching classes initiated by [PERSON] and [PERSON]. Corollary 7: _Let \(G\) and \(G^{\prime}\) be two switching equivalent graphs and denote by \((v_{1},\ldots,v_{\ell})\) a sequence of vertices such that \(G^{\ell}=G^{\prime}\) is true. Then, it holds that_  
\[tw(G^{\prime})\leq tw(G)+\ell\quad\text{and}\quad pw(G^{\prime})\leq pw(G)+\ell.\]