# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 1 Introduction  
A _graph parameter_ is a function that associates every graph with a non-negative integer. One of the most famous graph parameters is tree-width, which was defined by [PERSON] and [PERSON] [1]. Graphs of bounded tree-width are interesting from an algorithmic point of view, as several NP-complete graph problems can be solved in polynomial time for graph classes of bounded tree-width. For example, tree-decompositions allow for many efficient algorithms in dynamic programming [2, 3, 4, 5]. The same holds for the similar graph parameter path-width. This is because every path-decomposition can be interpreted as a special case of a tree-decomposition. Both parameters play a crucial role in the field of structural graph theory, especially in the graph minor theory of [PERSON] [6]. Trees and forests have tree-width at most one. Series-parallel graphs have tree-width at most two [7]. Outerplanar graphs (and subclasses such as cactus graphs and maximal outerplanar graphs) have tree-width at most two, and \(k\)-outerplanar graphs have tree-width at most \(3k-1\)[7]. Halin graphs have tree-width at most three [7]. For other classes of graphs with bounded tree-width, we refer the reader to the works of [PERSON] [8, 9, 7]. Determining whether the tree-width or path-width of a graph is at most a given value \(w\) is NP-complete [10]. However, for every fixed integer \(k\), one can decide in linear time whether a given graph \(G\) has tree-width or path-width \(k\) (see [PERSON] [11]). For anin-depth overview of tree-width and path-width, we again refer the reader to the work by [PERSON] [7]. A _graph transformation_\(f\) is a function that creates a new graph \(f(G_{1},\ldots,G_{n})\) from a number of \(n\geq 1\) input graphs \(G_{1},\ldots,G_{n}\). Examples of graph transformations include taking an induced subgraph of a graph, adding an edge to a graph, or generating the join of two graphs. A _graph operation_ is a graph transformation that is deterministic and invariant under isomorphism. Examples of graph operations include the edge complementation of a graph or generating the join of two graphs. Please note that by our definition, the two graph transformations that involve taking an induced subgraph of a graph and adding an edge to a graph are not graph operations. The graph theory books by [PERSON] and [PERSON] [12] and [PERSON] [13] provide a large number of graph transformations. The impact of graph operations, which can be defined by monadic second-order formulas (so-called MS transductions), on graph parameters can often be shown in a very short way. Unfortunately, the resulting bounds are typically rather imprecise [14; 15]. Transformations that reduce graphs can be used to characterize classes of graphs by forbidden subgraphs. For example, the property that a graph has tree-width at most \(k\) is preserved under the graph transformation \"taking minors\". This fact is used to show that the set of graphs of tree-width at most \(k\) can be characterized by a finite set of forbidden minors [6]. The effect of graph transformations on graph parameters has been well studied, e.g., for bandwidth [16], for tree-width [7], for clique-width [17; 18; 19], and for rank-width [18]. In this paper, we study the behavior of tree-width and path-width under various graph transformations and graph operations. We consolidate known results from various works and prove novel results. In doing so, this work provides a comprehensive overview of the effects of unary and binary graph transformations on tree-width and path-width. This paper is organized as follows. In Section 2, we recall the definitions of tree-width and path-width. In Section 3, we consider the effects of the following unary graph transformations on tree-width and path-width: vertex deletion, vertex addition, edge deletion, edge addition, subgraphs, vertex identification, edge contraction, edge subdivision, minors, powers of graphs, line graphs, edge complements, local complements, Seidel switching, and Seidel complementation.