# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 4 Split Graphs  
Let \(G\) be such a graph that \(V(G)=I\cup C\) and \(I\cap C=\emptyset\). If \(I\) is an independent set and \(C\) is a clique, \(G\) is a _split_ graph. Then, every maximal of \(G\) is either \(C\) itself, or the closed neighborhood \(N_{G}[x]\) of a vertex \(x\in I\). We use \(G=(I,C,E)\) to represent a split graph. The \(\{k\}\)-CTP, the \(k\)-FCTP, the SCTP, and the MCTP for split graphs are considered in this section. We also consider the \(\{k\}\)-DP, the \(k\)-TDP, the SDP, and the MDP for split graphs. For split graphs, the \(\{k\}\)-DP, the \(k\)-TDP, and the MDP are NP-complete [16; 17; 18], but the complexity of the SDP is still unknown. In the following, we examine the relationships between the \(\{k\}\)-CTP and the \(\{k\}\)-DP, the \(k\)-FCTP and the \(k\)-TDP, the SCTP and the SDP, and the MCTP and the MDP. Then, by the relationships, we prove the NP-completeness of the SDP, the \(\{k\}\)-CTP, the \(k\)-FCTP, the SCTP, and the MCTP for split graphs. We first consider the \(\{k\}\)-CTP and the \(k\)-FCTP and show in Theorems 3.2 and 3.2 that \(\tau_{\mathbb{C}}^{k}(G)=\gamma_{\times k}(G)\) and \(\tau_{\mathbb{C}}^{\{k\}}(G)=\gamma_{\{k\}}(G)\) for any split graph \(G\). Chordal graphs form a superclass of split graphs [19]. The cardinality of \(\mathbb{C}(G)\) is at most \(n\) for any chordal graph \(G\)[20]. The following lemma therefore holds trivially. Lemma 6: _The k-FCTP, the \(\{k\}\)-CTP, the SCTP, and the MCTP for chordal graphs are in NP._  
**Theorem 4**. : _Suppose that \(k\in\mathbb{N}\) and \(G=(I,C,E)\) is a split graph. Then, \(\tau_{\mathbb{C}}^{k}(G)=\gamma_{\times k}(G)\)._  
Proof. : Let \(S\) be a minimum \(k\)-FCTS of \(G\). Consider a vertex \(y\in I\). By the structure of \(G\), \(N_{\mathbb{C}}[y]\) is a maximal clique of \(G\). Then, \(|S\cap N_{\mathbb{C}}[y]|\geq k\). We now consider a vertex \(x\in C\). If \(C\
ot\in C(G)\), then there exists a vertex \(y\in I\) such that \(N_{\mathbb{C}}[y]=C\cup\{y\}\). Clearly, \(N_{\mathbb{C}}[y]\subseteq N_{\mathbb{C}}[x]\) and \(|S\cap N_{\mathbb{C}}[x]|\geq|S\cap N_{\mathbb{C}}[y]|\geq k\). If \(C\in C(G)\), then \(|S\cap N_{\mathbb{C}}[x]|\geq|S\cap C|\geq k\). Hence, \(S\) is a \(k\)-TDS of \(G\). We have \(\gamma_{\times k}(G)\leq\tau_{\mathbb{C}}^{k}(G)\). Let \(D\) be a minimum \(k\)-TDS of \(G\). Recall that the closed neighborhood of every vertex in \(I\) is a maximal clique. Then, \(D\) contains at least \(k\) vertices in the maximal clique \(N_{\mathbb{C}}[y]\) for every vertex \(y\in I\). If \(C\
ot\in C(G)\), \(D\) is clearly a \(k\)-FCTS of \(G\). Suppose that \(C\in C(G)\). We consider three cases as follows. Case 1: \(y\in I\setminus D\). Then, \(|D\cap C|\geq|D\cap N_{\mathbb{C}}(y)|\geq k\). The set \(D\) is a \(k\)-FCTS of \(G\). Case 2: \(y\in I\cap D\) and \(x\in N_{\mathbb{C}}(y)\setminus D\). Then, the set \(D^{\prime}=(D\setminus\{y\})\cup\{x\}\) is still a minimum \(k\)-TDS and \(|D^{\prime}\cap C|\geq|D^{\prime}\cap N_{\mathbb{C}}(y)|\geq k\). The set \(D^{\prime}\) is a \(k\)-FCTS of \(G\). Case 3: \(I\subseteq D\) and \(N_{\mathbb{C}}[y]\subseteq D\) for every \(y\in I\). Then, \(|D\cap C|\geq|D\cap N_{\mathbb{C}}(y)|\geq k-1\). Since \(C\in C(G)\), there exists \(x\in C\) such that \(y\
ot\in N_{\mathbb{C}}(x)\). If \(N_{\mathbb{C}}(x)\cap I=\emptyset\), then \(N_{\mathbb{C}}[x]=C\) and \(|D\cap C|=|D\cap N_{\mathbb{C}}[x]|\geq k\). Otherwise, let \(y^{\prime}\in N_{\mathbb{C}}(x)\cap I\). Then, \(x\in D\) and \(|D\cap C|\geq|D\cap N_{\mathbb{C}}(y)|+1\geq k\). The set \(D\) is a \(k\)-FCTS of \(G\). By the discussion of the three cases, we have \(\tau_{\mathbb{C}}^{k}(G)\leq\gamma_{\times k}(G)\). Hence, we obtain that \(\gamma_{\times k}(G)\leq\tau_{\mathbb{C}}^{k}(G)\) and \(\tau_{\mathbb{C}}^{k}(G)\leq\gamma_{\times k}(G)\). The theorem holds for split graphs. **Theorem 5**. : _Suppose that \(k\in\mathbb{N}\) and \(G=(I,C,E)\) is a split graph. Then, \(\tau_{\mathbb{C}}^{\{k\}}(G)=\gamma_{\{k\}}(G)\)._  
Proof.