# The Clique-Width of Minimal Series-Parallel Digraphs
## 3 Directed Clique-Width of Minimal Series-Parallel Digraphs (MSP DAGs)
* Label 3 is used for the set of vertices being neither sources nor sinks. * Label 4 is used for the set of isolated vertices. * Label 5 is used as an auxiliary label for label 2 for the first graph when we have to distinguish the labels from two combined graphs during the arc insertion operation. * Label 6 is used as an auxiliary label for label 1 for the second graph when we have to distinguish the labels from two combined graphs during the arc insertion operation. We define for every node \(\alpha\) of \(T(G)\) a directed clique-width 6-expression \(t_{\alpha}\) which defines the subgraph \(G[\alpha]\) of \(G\) defined by the subtree of \(T(G)\) rooted at \(\alpha\) such that all non-isolated sources are labeled by 1, all non-isolated sinks are labeled by 2, all vertices being neither sources nor sinks are labeled by 3, and all isolated vertices are labeled by 4. For every such \(t_{\alpha}\) we use two subexpressions \(t_{1,\alpha}\) and \(t_{2,\alpha}\), such that  
* \(t_{1,\alpha}\) defines the subgraph of \(G[\alpha]\) given by the non-isolated vertices and
* \(t_{2,\alpha}\) defines the subgraph of \(G[\alpha]\) given by isolated vertices. This allows us to obtain \(G[\alpha]\) by \(t_{\alpha}=t_{1,\alpha}\oplus t_{2,\alpha}\). Figure 3: Labels used in the proof of Theorem 1: Label 1 is used for the set of non-isolated sources, label 2 is used for the set of non-isolated sinks, label 3 is used for the set of vertices being neither sources nor sinks, and label 4 is used for the set of isolated vertices. First, we distinguish between leaf vertices and inner vertices of \(T(G)\):  
* Let \(\alpha\) be a leaf of \(T(G)\) which represents vertex \(v\) of \(G\). We define \[t_{1,\alpha} = \emptyset\] \[t_{2,\alpha} = 4(v)\] For the correctness we note that \(t_{\alpha}=t_{1,\alpha}\oplus t_{2,\alpha}\) defines digraph \(G[\alpha]\) and the single isolated vertex is labeled by 4. * Let \(\alpha\) be an internal node of \(T(G)\) and \(\alpha_{1}\), \(\alpha_{2}\) are respectively the left and right children of \(\alpha\). We will construct a directed clique-width 6-expression \(t_{\alpha}\) for \(G[\alpha]\) using a directed clique-width 6-expression \(t_{\alpha_{1}}\) for \(G[\alpha_{1}]\) and a directed clique-width 6-expression \(t_{\alpha_{2}}\) for \(G[\alpha_{2}]\). We can assume that for \(\alpha_{1}\) and \(\alpha_{2}\) we know the subexpression for the non-isolated and isolated part of \(G[\alpha_{1}]\) and \(G[\alpha_{2}]\), such that \[t_{\alpha_{1}}=t_{1,\alpha_{1}}\oplus t_{2,\alpha_{1}}\] and \[t_{\alpha_{2}}=t_{1,\alpha_{2}}\oplus t_{2,\alpha_{2}}.\] To illustrate our following constructions we use two digraphs \(G[\alpha_{1}]\) and \(G[\alpha_{2}]\) in Figure 3(a,b). Without loss of generality, and for simplification of reading, we represented in this figure each type of vertex (non-isolated source, non-isolated sink, neither source nor sink, isolated) by a single vertex. The labeling of the vertices using labels from \(\{1,\ldots,4\}\) obviously fulfills our given conditions. To construct a directed clique-width 6-expression \(t_{\alpha}\) for \(G[\alpha]\) we distinguish two cases according to the type of \(\alpha\):  
* Suppose that \(\alpha\) is a \(P\)-node. In this case, we define \(t_{\alpha}=t_{1,\alpha}\oplus t_{2,\alpha}\), where \[t_{1,\alpha} = t_{1,\alpha_{1}}\oplus t_{1,\alpha_{2}}\] \[t_{2,\alpha} = t_{2,\alpha_{1}}\oplus t_{2,\alpha_{2}}.\] Figure 3(c) illustrates the construction of \(G[\alpha]\) from the two digraphs shown in Figure 3(a,b) following the expressions \(t_{1,\alpha}\) and \(t_{2,\alpha}\). For the correctness we note that an \(P\)-node does not insert any new arcs in the disjoint union of \(G[\alpha_{1}]\) and \(G[\alpha_{2}]\), thus \(t_{\alpha}=t_{1,\alpha}\oplus t_{2,\alpha}\) defines the digraph \(G[\alpha]\).