# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 2 Suns  
In this section, we give equations to compute \(\tau_{\mathbb{C}}^{\{k\}}(G)\), \(\tau_{\mathbb{C}}^{k}(G)\), \(\tau_{\mathbb{C}}^{\mathbb{s}}(G)\), and \(\tau_{\mathbb{C}}^{-}(G)\) for any sun \(G\) and show that \(\tau_{\mathbb{C}}^{\{k\}}(G)=\gamma_{\{k\}}(G)\), \(\tau_{\mathbb{C}}^{k}(G)=\gamma_{\times k}(G)\), \(\tau_{\mathbb{C}}^{\mathbb{s}}(G)=\gamma_{\mathbb{s}}(G)\), and \(\tau_{\mathbb{C}}^{-}(G)=\gamma^{-}(G)\). Let \(p\in\mathbb{N}\) and \(G\) be a graph. An edge \(e\in E(G)\) is a _chord_ if \(e\) connects two non-consecutive vertices of a cycle in \(G\). If \(C\) has a chord for every cycle \(C\) consisting of more than three vertices, \(G\) is a _chordal_ graph. A _sun_\(G\) is a chordal graph whose vertices can be partitioned into \(W=\{w_{i}\mid 1\leq i\leq p\}\) and \(U=\{u_{i}\mid 1\leq i\leq p\}\) such that (1) \(W\) is an independent set, (2) the vertices \(u_{1},u_{2},\ldots,u_{p}\) of \(U\) form a cycle, and (3) every \(w_{i}\in W\) is adjacent to precisely two vertices \(u_{i}\) and \(u_{j}\), where \(j\equiv i+1\) (mod \(p\)). We use \(S_{p}=(W,U,E)\) to denote a sun. Then, \(|V(S_{p})|=2p\). If \(p\) is odd, \(S_{p}\) is an _odd_ sun; otherwise, it is an _even_ sun. Figure 1 shows two suns. **Lemma 1**. : _For any \(S_{p}=(W,U,E)\), \(\tau_{\mathbb{C}}^{2}(S_{p})=p\) and \(\tau_{\mathbb{C}}^{3}(S_{p})=2p\)._  
Proof. : It is straightforward to see that \(U\) is a minimum 2-FCTS and \(W\cup U\) is a minimum 3-FCTS of \(S_{p}\). This lemma therefore holds. **Lemma 2**. : _Suppose that \(k\in\mathbb{N}\) and \(k>1\). Then, \(\tau_{\mathbb{C}}^{\{k\}}(S_{p})=\lceil pk/2\rceil\) for any sun \(S_{p}=(W,U,E)\)._  
Proof. : Let \(i,j\in\{1,2,\ldots p\}\) such that \(j\equiv i+1\) (mod \(p\)). Since every \(w_{i}\in W\) is adjacent to precisely two vertices \(u_{i},u_{j}\in U\), \(N_{S_{p}}[w_{i}]=\{w_{i},u_{i},u_{j}\}\) is a maximal clique of \(S_{p}\). By contradiction, we can prove that there exists a minimum \(\{k\}\)-CTF \(f\) of \(S_{p}\) such that \(f(w_{i})=0\) for \(w_{i}\in W\). Since \(f(N_{S_{p}}[w_{i}])\geq k\) for \(1\leq i\leq p\), we have  
\[\tau_{\mathbb{C}}^{\{k\}}(S_{p})=\sum_{i=1}^{p}f(u_{i})=\frac{\sum_{i=1}^{p}f( N_{S_{p}}[w_{i}])}{2}\geq\frac{pk}{2}.\]  
Since \(\tau_{\mathbb{C}}^{\{k\}}(S_{p})\) is a nonnegative integer, \(\tau_{\mathbb{C}}^{\{k\}}(S_{p})\geq\lceil pk/2\rceil\). We define a function \(h:W\cup U\to\{0,1,\ldots,k\}\) by \(h(w_{i})=0\) for every \(w_{i}\in W\), \(h(u_{i})=\lceil k/2\rceil\) for \(u_{i}\in U\) with odd index \(i\) and \(h(u_{i})=\lfloor k/2\rfloor\) for every \(u_{i}\in U\) with even index \(i\). Clearly, a maximal clique \(Q\) of \(S_{n}\) is either the closed neighborhood of some vertex in \(W\) or a set of at least three vertices in \(U\). If \(Q=N_{S_{p}}[w_{i}]\) for some \(w_{i}\in W\), then \(h(Q)=\lceil k/2\rceil+\lfloor k/2\rfloor=k\). Suppose that \(Q\) is a set of at least three vertices in \(U\). Since \(k\geq 2\), \(h(Q)\geq 3\cdot\lfloor k/2\rfloor\geq k\). Therefore, \(h\) is a \(\{k\}\)-CTF of \(S_{p}\). We show the weight of \(h\) is \(\lceil pk/2\rceil\) by considering two cases as follows. Case 1: \(p\) is even. We have  
\[h(V(S_{p}))=\sum_{i=1}^{p}h(u_{i})=\frac{p}{2}\cdot(\lceil k/2\rceil+\lfloor k /2\rfloor)=\frac{pk}{2}.\]  
Case 2: \(p\) is odd. We have  
\[h(V(S_{p}))=\sum_{i=1}^{p}h(u_{i})=\frac{(p-1)}{2}\cdot k+\lceil k/2\rceil= \lceil pk/2\rceil.\]  
Following what we have discussed above, we know that \(h\) is a minimum \(\{k\}\)-CTF of \(S_{n}\) and thus \(\tau_{\mathbb{C}}^{\{k\}}(S_{p})=\lceil pk/2\rceil\). **Lemma 3**. : _For any sun \(S_{p}=(W,U,E)\), \(\tau_{\mathbb{C}}^{-}(S_{p})=\tau_{\mathbb{C}}^{s}(S_{p})=0\)._Proof. : For \(1\leq i\leq p\), \(N_{S_{p}}[w_{i}]\) is a maximal clique of \(S_{p}\). Let \(h\) be a minimum SCTF of \(S_{p}\). Then, \(\tau_{\mathbb{C}}^{s}(S_{p})=h(V(S_{p}))\). Note that \(h(N_{S_{p}}[w_{i}])\geq 1\) for \(1\leq i\leq p\).