# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 5 Doubly Chordal and Dually Chordal Graphs  
Assume that \(G\) is a graph with \(n\) vertices \(x_{1},x_{2},\ldots,x_{n}\). Let \(i\in\{1,2,\ldots,n\}\) and let \(G_{i}\) be the subgraph \(G[V(G)\setminus\{x_{1},x_{2},\ldots x_{i-1}\}]\). For every \(x\in V(G_{i})\), let \(N_{i}[x]=\{y\mid y\in(N_{G}[x]\setminus\{x_{1},x_{2},\ldots,x_{i-1}\})\}\). In \(G_{i}\), if there exists a vertex \(x_{j}\in N_{i}[x_{i}]\) such that \(N_{i}[x_{k}]\subseteq N_{i}[x_{j}]\) for every \(x_{k}\in N_{i}[x_{i}]\), then the ordering \((x_{1},x_{2},\ldots,x_{n})\) is a _maximum neighborhood ordering_ (abbreviated as MNO) of \(G\). A graph \(G\) is _dually chordal_[21] if and only if \(G\) has an MNO. It takes linear time to compute an MNO for any dually chordal graph [22]. A graph \(G\) is a _doubly chordal_ graph if \(G\) is both chordal and dually chordal [23]. Lemma 8 shows that a dually chordal graph is not necessarily a chordal graph or a clique perfect graph. Notice that the number of maximal cliques in a chordal graph is at most \(n\)[20], but the number of maximal cliques in a dually chordal graph can be exponential [24].  
Lemma 8: _For any dually graph \(G\), \(\tau_{C}(G)=\alpha_{C}(G)\), but \(G\) is not necessarily clique perfect or chordal._  
Proof: [PERSON] et al. [25] showed that the CTP is a particular case of the _clique \(r\)-domination problem_ and the CIP is a particular case of the _clique \(r\)-packing problem_. They also showed that the minimum cardinality of a clique \(r\)-dominating set of a dually chordal graph \(G\) is equal to the maximum cardinality of a clique \(r\)-packing set of \(G\). Therefore, \(\tau_{C}(G)=\alpha_{C}(G)\).  
Assume that \(H\) is a graph obtained by connecting every vertex of a cycle \(C_{4}\) of four vertices \(x_{1},x_{2},x_{3},x_{4}\) to a vertex \(x_{5}\). Clearly, the ordering \((x_{1},x_{2},x_{3},x_{4},x_{5})\) is an MNO and thus \(H\) is a dually chordal graph. The cycle \(C_{4}\) is an induced subgraph of \(H\) and does not have a chord. Moreover, \(\tau_{C}(H)=\alpha_{C}(H)=1\), but \(\tau_{C}(C_{4})=2\) and \(\alpha_{C}(C_{4})=1\). Hence, a dually chordal graph is not necessarily clique perfect or chordal.  
Theorem 8: _Suppose that \(k\in\mathbb{N}\) and \(k>1\). The \(k\)-FCTP on doubly chordal graphs is NP-complete._  
Proof: Suppose that \(G\) is a chordal graph. Let \(H\) be a graph such that \(V(H)=V(G)\cup\{x\}\) and \(E(H)=E(G)\cup\{(x,y)\mid y\in V(G)\}\). Clearly, \(H\) is a doubly chordal graph and we can construct \(H\) from \(G\) in linear time.  
Assume that \(S\) is a minimum \((k-1)\)-FCTS of \(G\). By the construction of \(H\), each maximal clique of \(H\) contains the vertex \(x\). Therefore, \(S\cup\{x\}\) is a \(k\)-FCTS of \(H\). Then \(\tau_{C}^{k}(H)\leq\tau_{C}^{k-1}(G)+1\).  
By contradiction, we can verify that there exists a minimum \(k\)-FCTS \(D\) of \(H\) such that \(x\in D\). Let \(S=D\setminus\{x\}\). Clearly, \(S\) is a \((k-1)\)-FCTS of \(G\). Then \(\tau_{C}^{k-1}(G)\leq\tau_{C}^{k}(H)-1\). Following what we have discussed above, we have \(\tau_{C}^{k}(H)=\tau_{C}^{k-1}(G)+1\). Notice that \(\tau_{C}(G)=\tau_{C}^{1}(G)\) and the CTP on chordal graphs is NP-complete [14]. Hence, the \(k\)-FCTP on doubly chordal graphs is NP-complete for doubly chordal graphs.  
Theorem 9: _For any doubly chordal graph \(G\), \(\tau_{C}^{\{k\}}(G)\) can be computed in linear time._  
Proof: The clique \(r\)-dominating problem on doubly chordal graphs can be solved in linear time [25]. The CTP is a particular case of the clique \(r\)-domination problem. Therefore, the CTP on doubly chordal graphs can also be solved in linear time. By Lemmas 4 and 8, the theorem holds.