# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 4 Split Graphs
: We can verify by contradiction that \(G\) has a minimum-weight \(\{k\}\)-CTF \(f\) and a minimum-weight \(\{k\}\)-DF \(g\) of \(G\) such that \(f(y)=0\) and \(g(y)=0\) for every \(y\in I\). By the structure of \(G\), \(N_{\mathbb{C}}[y]\in C(G)\) for every \(y\in I\). Then, \(f(N_{\mathbb{C}}[y])\geq k\) and \(g(N_{\mathbb{C}}[y])\geq k\). Since \(f(y)=0\) and \(g(y)=0\), \(f(N_{\mathbb{C}}(y))\geq k\) and \(g(N_{\mathbb{C}}(y))\geq k\). For every \(y\in I\), \(N_{\mathbb{C}}(y)\subseteq C\) and \(f(C)\geq f(N_{\mathbb{C}}(y))\geq k\). For every \(x\in C\), \(f(N_{\mathbb{C}}[x])\geq f(C)\geq k\). Therefore, the function \(f\) is also a \(\{k\}\)-DF of \(G\). We have \(\gamma_{\{k\}}(G)\leq\tau_{\mathbb{C}}^{\{k\}}(G)\). We now consider \(g(C)\) for the clique \(C\). If \(C\
ot\in C(G)\), the function \(g\) is clearly a \(\{k\}\)-CTF of \(G\). Suppose that \(C\in C(G)\). Notice that \(g\) is a \(\{k\}\)-DF and \(g(y)=0\) for every \(y\in I\). Then, \(g(C)=g(N_{\mathbb{C}}[x])\geq k\) for any vertex \(x\in C\). Therefore, \(g\) is also a \(\{k\}\)-CTF of \(G\). We have \(\tau_{\mathbb{C}}^{\{k\}}(G)\leq\gamma_{\{k\}}(G)\). Following what we have discussed above, we know that \(\tau_{\mathbb{C}}^{\{k\}}(G)=\gamma_{\{k\}}(G)\). **Corollary 3**. : _The \(\{k\}\)-CTP and the \(k\)-FCTP are NP-complete for split graphs._  
Proof. : The corollary holds by Theorems 4 and 5 and the NP-completeness of the \(\{k\}\)-DP and the \(k\)-TDP for split graphs [16; 18]. A graph \(G\) is a _complete_ if \(C(G)=\{V(G)\}\). Let \(G\) be a complete graph and let \(x\in V(G)\). The vertex set \(V(G)\) is the union of the sets \(\{x\}\) and \(V(G)\setminus\{x\}\). Clearly, \(\{x\}\) is an independent set and \(V(G)\setminus\{x\}\) is a clique of \(G\). Therefore, complete graphs are split graphs. It is easy to verify the Lemma 7. **Lemma 7**. : _If \(G\) is a complete graph and \(k\in\mathbb{N}\), then_  
\(\tau_{\mathbb{C}}^{k}(G)=\gamma_{\times k}(G)=k\) _for_ \(k\leq n\)_;_  
\(\tau_{\mathbb{C}}^{\{k\}}(G)=\gamma_{\{k\}}(G)=k\)_;_  
\(\tau_{\mathbb{C}}^{\{}C}(G)=\gamma^{-}(G)=1\)_;_  
\(\tau_{\mathbb{C}}^{\{}\)_\(\mathbb{C}}(G)=\gamma_{s}(G)=\left\{ \begin{array}{ll}1&\mbox{ if $n$ is odd;}\\ 2&\mbox{otherwise.}\end{array} \right.\)__For split graphs, however, the signed and minus domination numbers are not necessarily equal to the signed and minus clique transversal numbers, respectively. Figure 2 shows a split graph \(G\) with \(\tau_{\mathbb{C}}^{s}(G)=\tau_{\mathbb{C}}^{-}(G)=-3\). However, \(\gamma_{s}(G)=\gamma^{-}(G)=1\). We therefore introduce \(H_{1}\)-_split_ graphs and show in Theorem 6 that their signed and minus domination numbers are equal to the signed and minus clique transversal numbers, respectively. \(H_{1}\)-split graphs are motivated by the graphs in [17] for proving the NP-completeness of the MDP on split graphs. Figure 3 shows an \(H_{1}\)-split graph. **Definition 9**. : _Suppose that \(G=(I,C,E)\) is a split graph with \(3p+3\ell+2\) vertices. Let \(U\), \(S\), \(X\), and \(Y\) be pairwise disjoint subsets of \(V(G)\) such that \(U=\{u_{i}\mid 1\leq i\leq p\}\), \(S=\{s_{i}\mid 1\leq i\leq\ell\}\), \(X=\{x_{i}\mid 1\leq i\leq p+\ell+1\}\), and \(Y=\{y_{i}\mid 1\leq i\leq p+\ell+1\}\). The graph \(G\) is an \(H_{1}\)-split graph if \(V(G)=U\cup S\cup X\cup Y\) and \(G\) entirely satisfies the following three conditions. (1) \(I=S\cup Y\) and \(C=U\cup X\). (2) \(N_{G}(y_{i})=\{x_{i}\}\) for \(1\leq i\leq p+\ell+1\). (3) \(|N_{G}(s_{i})\cap U|=3\) and \(N_{G}(s_{i})\cap X=\{x_{i}\}\) for \(1\leq i\leq\ell\)._  
**Theorem 6**. : _For any \(H_{1}\)-split graph \(G=(I,C,E)\), \(\tau_{\mathbb{C}}^{s}(G)=\gamma_{s}(G)\) and \(\tau_{\mathbb{C}}^{-}(G)=\gamma^{-}(G)\)._  
Proof. : We first prove \(\tau_{\mathbb{C}}^{s}(G)=\gamma_{s}(G)\). Let \(G=(I,C,E)\) be an \(H_{1}\)-split graph.