Next Article in Journal
Simheuristics Approaches for Efficient Decision-Making Support in Materials Trading Networks
Next Article in Special Issue
A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k < 2
Previous Article in Journal
Dynamic Shortest Paths Methods for the Time-Dependent TSP
Previous Article in Special Issue
Efficient Approaches to the Mixture Distance Problem

Open AccessArticle

# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs

Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan
Received: 9 December 2020 / Revised: 4 January 2021 / Accepted: 11 January 2021 / Published: 13 January 2021

## Abstract

This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the ${k}$-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the ${k}$-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the ${k}$-clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.

## 1. Introduction

Every graph $G = ( V , E )$ in this paper is finite, undirected, connected, and has at most one edge between any two vertices in G. We assume that the vertex set V and edge set E of G contain n vertices and m edges. They can also be denoted by $V ( G )$ and $E ( G )$. A graph $G ′ = ( V ′ , E ′ )$ is an induced subgraph of G denoted by $G [ V ′ ]$ if $V ′ ⊆ V$ and $E ′$ contains all the edge $( x , y ) ∈ E$ for $x , y ∈ V ′$. Two vertices $x , y ∈ V$ are adjacent or neighbors if $( x , y ) ∈ E$. The sets $N G ( x ) = { y ∣ ( x , y ) ∈ E }$ and $N G [ x ] = N G ( x ) ∪ { x }$ are the neighborhood and closed neighborhood of a vertex x in G, respectively. The number $d e g G ( x ) = | N G ( x ) |$ is the degree of x in G. If $d e g G ( x ) = k$ for every $x ∈ V$, then G is k-regular. Particularly, cubic graphs are an alternative name for 3-regular graphs.
A subset S of V is a clique if $( x , y ) ∈ E$ for $x , y ∈ S$. Let Q be a clique of G. If $Q ∩ Q ′ ≠ Q$ for any other clique $Q ′$ of G, then Q is a maximal clique. We use $C ( G )$ to represent the set ${ C ∣ C$ is a maximal clique of $G }$. A clique $S ∈ C ( G )$ is a maximum clique if $| S | ≥ | S ′ |$ for every $S ′ ∈ C ( G )$. The number $ω ( G ) = max { | S | ∣ S ∈ C ( G ) }$ is the clique number of G. A set $D ⊆ V$ is a clique transversal set (abbreviated as CTS) of G if $| C ∩ D | ≥ 1$ for every $C ∈ C ( G )$. The number $τ C ( G ) = min { | S | ∣ S$ is a CTS of $G }$ is the clique transversal number of G. The clique transversal problem (abbreviated as CTP) is to find a minimum CTS for a graph. A set $S ⊆ C ( G )$ is a clique independent set (abbreviated as CIS) of G if $| S | = 1$ or $| S | ≥ 2$ and $C ∩ C ′ = ∅$ for $C , C ′ ∈ S$. The number $α C ( G ) = max { | S | ∣ S$ is a CIS of $G }$ is the clique independence number of G. The clique independence problem (abbreviated as CIP) is to find a maximum CIS for a graph.
The CTP and the CIP have been widely studied. Some studies on the CTP and the CIP consider imposing some additional constraints on CTS or CIS, such as the maximum-clique independence problem (abbreviated as MCIP), the k-fold clique transversal problem (abbreviated as k-FCTP), and the maximum-clique transversal problem (abbreviated as MCTP).
Definition 1
([1,2]). Suppose that $k ∈ N$ is fixed and G is a graph. A set $D ⊆ V ( G )$ is a k-fold clique transversal set (abbreviated as k-FCTS) of G if $| C ∩ D | ≥ k$ for $C ∈ C ( G )$. The number $τ C k ( G ) = m i n { | S | ∣ S$ is a k-FCTS of $G }$ is the k-fold clique transversal number of G. The k-FCTP is to find a minimum k-FCTS for a graph.
Definition 2
([3,4]). Suppose that G is a graph. A set $D ⊆ V ( G )$ is a maximum-clique transversal set (abbreviated as MCTS) of G if $| C ∩ D | ≥ 1$ for $C ∈ C ( G )$ with $| C | = ω ( G )$. The number $τ M ( G ) = m i n { | S | ∣ S$ is an MCTS of $G }$ is the maximum-clique transversal number of G. The MCTP is to find a minimum MCTS for a graph. A set $S ⊆ C ( G )$ is a maximum-clique independent set (abbreviated as MCIS) of G if $| C | = ω ( G )$ for $C ∈ S$ and $C ∩ C ′ = ∅$ for $C , C ′ ∈ S$. The number $α M ( G ) = m a x { | S | ∣ S$ is an MCIS of $G }$ is the maximum-clique independence number of G. The MCIP is to find a maximum MCIS for a graph.
The k-FCTP on balanced graphs can be solved in polynomial time [2]. The MCTP has been studied in [3] for several well-known graph classes and the MCIP is polynomial-time solvable for any graph H with $τ M ( H ) = α M ( H )$ [4]. Assume that $Y ⊆ R$ and $f : X → Y$ is a function. Let $f ( X ′ ) = ∑ x ∈ X f ( x )$ for $X ′ ⊆ X$, and let $f ( X )$ be the weight of f. A CTS of G can be expressed as a function f whose domain is $V ( G )$ and range is ${ 0 , 1 }$, and $f ( C ) ≥ 1$ for $C ∈ C ( G )$. Then, f is a clique transversal function (abbreviated as CTF) of G and $τ C ( G ) = min { f ( V ( G ) ) ∣ f$ is a CTF of $G }$. Several types of CTF have been studied [4,5,6,7]. The following are examples of CTFs.
Definition 3.
Suppose that $k ∈ N$ is fixed and G is a graph. A function f is a ${ k }$-clique transversal function (abbreviated as ${ k }$-CTF) of G if the domain and range of f are $V ( G )$ and ${ 0 , 1 , 2 , … , k }$, respectively, and $f ( C ) ≥ k$ for $C ∈ C ( G )$. The number $τ C { k } ( G ) = m i n { f ( V ( G ) ) ∣ f$ is a ${ k }$-CTF of $G }$ is the ${ k }$-clique transversal number of G. The ${ k }$-clique transversal problem (abbreviated as ${ k }$-CTP) is to find a minimum-weight ${ k }$-CTF for a graph.
Definition 4.
Suppose that G is a graph. A function f is a signed clique transversal function (abbreviated as SCTF) of G if the domain and range of f are $V ( G )$ and ${ − 1 , 1 }$, respectively, and $f ( C ) ≥ 1$ for $C ∈ C ( G )$. If the domain and range of f are $V ( G )$ and ${ − 1 , 0 , 1 }$, respectively, and $f ( C ) ≥ 1$ for $C ∈ C ( G )$, then f is a minus clique transversal function (abbreviated as MCTF) of G. The number $τ C s ( G ) = m i n { f ( V ( G ) ) ∣ f$ is an SCTF of $G }$ is the signed clique transversal number of G. The minus clique transversal number of G is $τ C − ( G ) = m i n { f ( V ( G ) ) ∣ f$ is an MCTF of $G }$. The signed clique transversal problem (abbreviated as SCTP) is to find a minimum-weight SCTF for a graph. The minus clique transversal problem (abbreviated as MCTP) is to find a minimum-weight MCTF for a graph.
Lee [4] introduced some variations of the k-FCTP, the ${ k }$-CTP, the SCTP, and the MCTP, but those variations are dedicated to maximum cliques in a graph. The MCTP on chordal graphs is NP-complete, while the MCTP on block graphs is linear-time solvable [7]. The MCTP and SCTP are linear-time solvable for any strongly chordal graph G if a strong elimination ordering of G is given [5]. The SCTP is NP-complete for doubly chordal graphs [6] and planar graphs [5].
According to what we have described above, there are very few algorithmic results regarding the k-FCTP, the ${ k }$-CTP, the SCTP, and the MCTP on graphs. This motivates us to study the complexities of the k-FCTP, the ${ k }$-CTP, the SCTP, and the MCTP. This paper also studies the MCTP and MCIP for some graphs and investigates the relationships between different dominating functions and CTFs.
Definition 5.
Suppose that $k ∈ N$ is fixed and G is a graph. A set $S ⊆ V ( G )$ is a k-tuple dominating set (abbreviated as k-TDS) of G if $| S ∩ N G [ x ] | ≥ 1$ for $x ∈ V ( G )$. The number $γ × k ( G ) = m i n { | S | ∣ S$ is a k-TDS of $G }$ is the k-tuple domination number of G. The k-tuple domination problem (abbreviated as k-TDP) is to find a minimum k-TDS for a graph.
Notice that a dominating set of a graph G is a 1-TDS. The domination number $γ ( G )$ of G is $γ × 1 ( G )$.
Definition 6.
Suppose that $k ∈ N$ is fixed and G is a graph. A function f is a ${ k }$-dominating function (abbreviated as ${ k }$-DF) of G if the domain and range of f are $V ( G )$ and ${ 0 , 1 , 2 , … , k }$, respectively, and $f ( N G [ x ] ) ≥ k$ for $x ∈ V ( G )$. The number $γ { k } ( G ) = m i n { f ( V ( G ) ) ∣ f$ is a ${ k }$-DF of $G }$ is the ${ k }$-domination number of G. The ${ k }$-domination problem (abbreviated as ${ k }$-DP) is to find a minimum-weight ${ k }$-DF for a graph.
Definition 7.
Suppose that G is a graph. A function f is a signed dominating function (abbreviated as SDF) of G if the domain and range of f are $V ( G )$ and ${ − 1 , 1 }$, respectively, and $f ( N G [ x ] ) ≥ 1$ for $x ∈ V ( G )$. If the domain and range of f are $V ( G )$ and ${ − 1 , 0 , 1 }$, respectively, and $f ( N G [ x ] ) ≥ 1$ for $x ∈ V ( G )$, then f is a minus dominating function (abbreviated as MDF) of G. The number $γ s ( G ) = m i n { f ( V ( G ) ) ∣ f$ is an SDF of $G }$ is the signed domination number of G. The minus domination number of G is $γ − ( G ) = m i n { f ( V ( G ) ) ∣ f$ is an MDF of $G }$. The signed domination problem (abbreviated as SDP) is to find a minimum-weight SDF for a graph. The minus domination problem (abbreviated as MDP) is to find a minimum-weight MDF for a graph.
Our main contributions are as follows.
1.
We prove in Section 2 that $γ − ( G ) = τ C − ( G )$ and $γ s ( G ) = τ C s ( G )$ for any sun G. We also prove that $γ × k ( G ) = τ C k ( G )$ and $γ { k } ( G ) = τ C { k } ( G )$ for any sun G if $k > 1$.
2.
We prove in Section 3 that $τ C { k } ( G ) = k τ C ( G )$ for any graph G with $τ C ( G ) = α C ( G )$. Then, $τ C { k } ( G )$ is polynomial-time solvable if $τ C ( G )$ can be computed in polynomial time. We also prove that the SCTP is a special case of the generalized clique transversal problem [8]. Therefore, the SCTP for a graph H can be solved in polynomial time if the generalized transversal problem for H is polynomial-time solvable.
3.
We show in Section 4 that $γ × k ( G ) = τ C k ( G )$ and $γ { k } ( G ) = τ C { k } ( G )$ for any split graph G. Furthermore, we introduce $H 1$-split graphs and prove that $γ − ( H ) = τ C − ( H )$ and $γ s ( H ) = τ C s ( H )$ for any $H 1$-split graph H. We prove the NP-completeness of SCTP for split graphs by showing that the SDP on $H 1$-split graphs is NP-complete.
4.
We show in Section 5 that $τ C { k } ( G )$ for a doubly chordal graph G can be computed in linear time, but the k-FCTP is NP-complete for doubly chordal graphs as $k > 1$. Notice that the CTP is a special case of the k-FCTP and the ${ k }$-CTP when $k = 1$, and thus $τ C ( G ) = τ C 1 ( G ) = τ C { 1 } ( G )$ for any graph G.
5.
We present other NP-completeness results in Section 6 and Section 7 for k-trees with unbounded k and subclasses of total graphs, line graphs, and planar graphs. These results can refine the “borderline” between P and NP for the considered problems and graphs classes or their subclasses.

## 2. Suns

In this section, we give equations to compute $τ C { k } ( G )$, $τ C k ( G )$, $τ C s ( G )$, and $τ C − ( G )$ for any sun G and show that $τ C { k } ( G ) = γ { k } ( G )$, $τ C k ( G ) = γ × k ( G )$, $τ C s ( G ) = γ s ( G )$, and $τ C − ( G ) = γ − ( G )$.
Let $p ∈ N$ and G be a graph. An edge $e ∈ 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 ∣ 1 ≤ i ≤ p }$ and $U = { u i ∣ 1 ≤ i ≤ p }$ such that (1) W is an independent set, (2) the vertices $u 1 , u 2 , … , u p$ of U form a cycle, and (3) every $w i ∈ W$ is adjacent to precisely two vertices $u i$ and $u j$, where $j ≡ i + 1$ (mod p). We use $S p = ( W , U , E )$ to denote a sun. Then, $| V ( S p ) | = 2 p$. 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 sun $S p = ( W , U , E )$, $τ C 2 ( S p ) = p$ and $τ C 3 ( S p ) = 2 p$.
Proof.
It is straightforward to see that U is a minimum 2-FCTS and $W ∪ U$ is a minimum 3-FCTS of $S p$. This lemma therefore holds. □
Lemma 2.
Suppose that $k ∈ N$ and $k > 1$. Then, $τ C { k } ( S p ) = ⌈ p k / 2 ⌉$ for any sun $S p = ( W , U , E )$.
Proof.
Let $i , j ∈ { 1 , 2 , … p }$ such that $j ≡ i + 1$ (mod p). Since every $w i ∈ W$ is adjacent to precisely two vertices $u i , u j ∈ 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 ∈ W$. Since $f ( N S p [ w i ] ) ≥ k$ for $1 ≤ i ≤ p$, we have
$τ C { k } ( S p ) = ∑ i = 1 p f ( u i ) = ∑ i = 1 p f ( N S p [ w i ] ) 2 ≥ p k 2 .$
Since $τ C { k } ( S p )$ is a nonnegative integer, $τ C { k } ( S p ) ≥ ⌈ p k / 2 ⌉$.
We define a function $h : W ∪ U → { 0 , 1 , … , k }$ by $h ( w i ) = 0$ for every $w i ∈ W$, $h ( u i ) = ⌈ k / 2 ⌉$ for $u i ∈ U$ with odd index i and $h ( u i ) = ⌊ k / 2 ⌋$ for every $u i ∈ 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 ∈ W$, then $h ( Q ) = ⌈ k / 2 ⌉ + ⌊ k / 2 ⌋ = k$. Suppose that Q is a set of at least three vertices in U. Since $k ≥ 2$, $h ( Q ) ≥ 3 · ⌊ k / 2 ⌋ ≥ k$. Therefore, h is a ${ k }$-CTF of $S p$. We show the weight of h is $⌈ p k / 2 ⌉$ by considering two cases as follows.
Case 1: p is even. We have
$h ( V ( S p ) ) = ∑ i = 1 p h ( u i ) = p 2 · ⌈ k / 2 ⌉ + ⌊ k / 2 ⌋ = p k 2 .$
Case 2: p is odd. We have
$h ( V ( S p ) ) = ∑ i = 1 p h ( u i ) = ( p − 1 ) 2 · k + ⌈ k / 2 ⌉ = ⌈ p k / 2 ⌉ .$
Following what we have discussed above, we know that h is a minimum ${ k }$-CTF of $S n$ and thus $τ C { k } ( S p ) = ⌈ p k / 2 ⌉$. □
Lemma 3.
For any sun $S p = ( W , U , E )$, $τ C − ( S p ) = τ C s ( S p ) = 0 .$
Proof.
For $1 ≤ i ≤ p$, $N S p [ w i ]$ is a maximal clique of $S p$. Let h be a minimum SCTF of $S p$. Then, $τ C s ( S p ) = h ( V ( S p ) )$. Note that $h ( N S p [ w i ] ) ≥ 1$ for $1 ≤ i ≤ p$. We have
$h ( V ( S p ) ) = ∑ i = 1 p h ( N S p [ w i ] ) − ∑ i = 1 p h ( u i ) ≥ p − ∑ i = 1 p h ( u i ) .$
Since $∑ i = 1 p h ( u i ) ≤ p$, we have $τ C s ( S p ) ≥ 0$. Let f be an SCTF of $S p$ such that $f ( u i ) = 1$ and $f ( w i ) = − 1$ for $1 ≤ i ≤ p$. The weight of f is 0. Then f is a minimum SCTF of $S p$. Hence, $τ C − ( S p ) = 0$ and $τ C s ( S p ) = 0$. The proof for $τ C − ( G ) = 0$ is analogous to that for $τ C s ( G ) = 0$. □
Theorem 1
(Lee and Chang [9]). Let $S p$ be a sun. Then,
(1)
$γ − ( S p ) = γ s ( S p ) = 0$;
(2)
$γ { k } ( S p ) = ⌈ p k / 2 ⌉$;
(3)
$γ × 1 ( S p ) = ⌈ p / 2 ⌉$, $γ × 2 ( S p ) = p$ and $γ × 3 ( S p ) = 2 p$.
Corollary 1.
Let$S p$be a sun. Then,
(1)
$γ − ( S p ) = τ C − ( S p ) = γ s ( S p ) = τ C s ( S p ) = 0$;
(2)
$γ { k } ( S p ) = τ C { k } ( S p ) = ⌈ p k / 2 ⌉$ for $k > 1$;
(3)
$γ × 2 ( S p ) = τ C 2 ( S p ) = p$ and $γ × 3 ( S p ) = τ C 3 ( S p ) = 2 p$.
Proof.
The corollary holds by Lemmas 1–3 and Corollary 1. □

## 3. Clique Perfect Graphs

Let $G$ be the set of all induced subgraphs of G. If $τ C ( H ) = α C ( H )$ for every $H ∈ G$, then G is clique perfect. In this section, we study the ${ k }$-CTP for clique perfect graphs and the SCTP for balanced graphs.
Lemma 4.
Let G be such a graph that $τ C ( G ) = α C ( G )$. Then, $τ C { k } ( G ) = k τ C ( G )$.
Proof.
Assume that D is a minimum CTS of G. Then, $| D | = τ C ( G )$. Let $x ∈ V ( G )$ and let f be a function whose domain is $V ( G )$ and range is ${ 0 , 1 , … , k }$, and $f ( x ) = k$ if $x ∈ D$; otherwise, $f ( x ) = 0$. Clearly, f is a ${ k }$-CTF of G. We have $τ C { k } ( G ) ≤ k τ C ( G )$.
Assume that f is a minimum-weight ${ k }$-CTF of G. Then, $f ( V ( G ) ) = τ C { k } ( G )$ and $f ( C ) ≥ k$ for every $C ∈ C ( G )$. Let $S = { C 1 , C 2 , … , C ℓ }$ be a maximum CIS of G. We know that $| S | = ℓ = α C ( G )$ and $∑ i = 1 ℓ f ( C i ) ≤ f ( V ( G ) )$. Therefore, $k τ C ( G ) = k α C ( G ) = k ℓ ≤ ∑ i = 1 ℓ f ( C i ) ≤ f ( V ( G ) ) = τ C { k } ( G )$. Following what we have discussed above, we know that $τ C { k } ( G ) = k τ C ( G )$. □
Theorem 2.
If a graph G is clique perfect, $τ C { k } ( G ) = k τ C ( G )$.
Proof.
Since G is clique perfect, $τ C ( G ) = α C ( G )$. Hence, the theorem holds by Lemma 4. □
Corollary 2.
The ${ k }$-CTP is polynomial-time solvable for distance-hereditary graphs, balanced graphs, strongly chordal graphs, comparability graphs, and chordal graphs without odd suns.
Proof.
Distance-hereditary graphs, balanced graphs, strongly chordal graphs, comparability graphs, and chordal graphs without odd suns are clique perfect, and the CTP can be solved in polynomial time for them [10,11,12,13,14]. The corollary therefore holds. □
Definition 8.
Suppose that R is a function whose domain is $C ( G )$ and range is ${ 0 , 1 , … , ω ( G ) }$. If $R ( C ) ≤ | C |$ for every $C ∈ C ( G )$, then R is a clique-size restricted function (abbreviated as CSRF) of G. A set $D ⊆ V ( G )$ is an R-clique transversal set (abbreviated as R-CTS) of G if R is a CSRF of G and $| D ∩ C | ≥ R ( C )$ for every $C ∈ C ( G )$. Let $τ R ( G ) = m i n { | D | ∣ D$ is an R-CTS of $G }$. The generalized clique transversal problem (abbreviated as GCTP) is to find a minimum R-CTS for a graph G with a CSRF R.
Lemma 5.
Let G be a graph with a CSRF R. If $R ( C ) = ⌈ ( | C | + 1 ) / 2 ⌉$ for every $C ∈ C ( G )$, then $τ C s ( G ) = 2 τ R ( G ) − n$.
Proof.
Assume that D is a minimum R-CTS of G. Then, $| D | = τ R ( G )$. Let $x ∈ V ( G )$ and let f be a function of G whose domain is $V ( G )$ and range is ${ − 1 , 1 }$, and $f ( x ) = 1$ if $x ∈ D$; otherwise, $f ( x ) = − 1$. Since $| D ∩ C | ≥ ⌈ ( | C | + 1 ) / 2 ⌉$ for every $C ∈ C ( G )$, there are at least $⌈ ( | C | + 1 ) / 2 ⌉$ vertices in C with the function value 1. Therefore, $f ( C ) ≥ 1$ for every $C ∈ C ( G )$, and f is an SCTF of G. Then, $τ C s ( G ) ≤ 2 τ R ( G ) − n$.
Assume that h is a minimum-weight SCTF of G. Clearly, $h ( V ( G ) ) = τ C s ( G )$. Since $h ( C ) ≥ 1$ for every $C ∈ C ( G )$, C contains at least $⌈ ( | C | + 1 ) ⌉ / 2$ vertices with the function value 1. Let $D = { x ∣ h ( x ) = 1 , x ∈ V ( G ) }$. The set D is an R-CTS of G. Therefore, $2 τ R ( G ) − n ≤ 2 | D | − n = τ C s ( G )$. Hence, we have $τ C s ( G ) = 2 τ R ( G ) − n$. □
Theorem 3.
The SCTP on balanced graphs can be solved in polynomial time.
Proof.
Suppose that a graph G has n vertices $v 1 , v 2 , … , v n$ and maximal cliques $C 1 , C 2 , … , C ℓ$. Let $i ∈ { 1 , 2 , … , ℓ }$ and $j ∈ { 1 , 2 , … , n }$. Let M be an $ℓ × n$ matrix such that an element $M ( i , j )$ of M is one if the maximal clique $C i$ contains the vertex $v j$, and $M ( i , j ) = 0$ otherwise. We call M the clique matrix of G. If the clique matrix M of G does not contain a square submatrix of odd order with exactly two ones per row and column, then M is a balanced matrix and G is a balanced graph. We formulae the GCTP on a balanced graph G with a CSRF R as the following integer programming problem:
where $C = ( R ( C 1 ) , R ( C 2 ) , … , R ( C ℓ ) )$ is a column vector and $X = ( x 1 , x 2 , … , x n )$ is a column vector such that $x i$ is either 0 or 1. Since the matrix M is balanced, an optimal 0–1 solution of the integer programming problem above can be found in polynomial time by the results in [15]. By Lemma 5, we know that the SCTP on balanced graphs can be solved in polynomial time. □

## 4. Split Graphs

Let G be such a graph that $V ( G ) = I ∪ C$ and $I ∩ C = ∅$. 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 ∈ 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 4 and 5 that $τ C k ( G ) = γ × k ( G )$ and $τ C { k } ( G ) = γ { k } ( G )$ for any split graph G. Chordal graphs form a superclass of split graphs [19]. The cardinality of $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 ∈ N$ and $G = ( I , C , E )$ is a split graph. Then, $τ C k ( G ) = γ × k ( G )$.
Proof.
Let S be a minimum k-FCTS of G. Consider a vertex $y ∈ I$. By the structure of G, $N G [ y ]$ is a maximal clique of G. Then, $| S ∩ N G [ y ] | ≥ k$. We now consider a vertex $x ∈ C$. If $C ∉ C ( G )$, then there exists a vertex $y ∈ I$ such that $N G [ y ] = C ∪ { y }$. Clearly, $N G [ y ] ⊆ N G [ x ]$ and $| S ∩ N G [ x ] | ≥ | S ∩ N G [ y ] | ≥ k$. If $C ∈ C ( G )$, then $| S ∩ N G [ x ] | ≥ | S ∩ C | ≥ k$. Hence, S is a k-TDS of G. We have $γ × k ( G ) ≤ τ 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 G [ y ]$ for every vertex $y ∈ I$. If $C ∉ C ( G )$, D is clearly a k-FCTS of G. Suppose that $C ∈ C ( G )$. We consider three cases as follows.
Case 1: $y ∈ I \ D$. Then, $| D ∩ C | ≥ | D ∩ N G ( y ) | ≥ k$. The set D is a k-FCTS of G.
Case 2: $y ∈ I ∩ D$ and $x ∈ N G ( y ) \ D$. Then, the set $D ′ = ( D \ { y } ) ∪ { x }$ is still a minimum k-TDS and $| D ′ ∩ C | ≥ | D ′ ∩ N G ( y ) | ≥ k$. The set $D ′$ is a k-FCTS of G.
Case 3: $I ⊆ D$ and $N G [ y ] ⊆ D$ for every $y ∈ I$. Then, $| D ∩ C | ≥ | D ∩ N G ( y ) | ≥ k − 1$. Since $C ∈ C ( G )$, there exists $x ∈ C$ such that $y ∉ N G ( x )$. If $N G ( x ) ∩ I = ∅$, then $N G [ x ] = C$ and $| D ∩ C | = | D ∩ N G [ x ] | ≥ k$. Otherwise, let $y ′ ∈ N G ( x ) ∩ I$. Then, $x ∈ D$ and $| D ∩ C | ≥ | D ∩ N G ( y ) | + 1 ≥ k$. The set D is a k-FCTS of G.
By the discussion of the three cases, we have $τ C k ( G ) ≤ γ × k ( G )$. Hence, we obtain that $γ × k ( G ) ≤ τ C k ( G )$ and $τ C k ( G ) ≤ γ × k ( G )$. The theorem holds for split graphs. □
Theorem 5.
Suppose that $k ∈ N$ and $G = ( I , C , E )$ is a split graph. Then, $τ C { k } ( G ) = γ { k } ( G )$.
Proof.
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 ∈ I$. By the structure of G, $N G [ y ] ∈ C ( G )$ for every $y ∈ I$. Then, $f ( N G [ y ] ) ≥ k$ and $g ( N G [ y ] ) ≥ k$. Since $f ( y ) = 0$ and $g ( y ) = 0$, $f ( N G ( y ) ) ≥ k$ and $g ( N G ( y ) ) ≥ k$.
For every $y ∈ I$, $N G ( y ) ⊆ C$ and $f ( C ) ≥ f ( N G ( y ) ) ≥ k$. For every $x ∈ C$, $f ( N G [ x ] ) ≥ f ( C ) ≥ k$. Therefore, the function f is also a ${ k }$-DF of G. We have $γ { k } ( G ) ≤ τ C { k } ( G )$. We now consider $g ( C )$ for the clique C. If $C ∉ C ( G )$, the function g is clearly a ${ k }$-CTF of G. Suppose that $C ∈ C ( G )$. Notice that g is a ${ k }$-DF and $g ( y ) = 0$ for every $y ∈ I$. Then, $g ( C ) = g ( N G [ x ] ) ≥ k$ for any vertex $x ∈ C$. Therefore, g is also a ${ k }$-CTF of G. We have $τ C { k } ( G ) ≤ γ { k } ( G )$. Following what we have discussed above, we know that $τ C { k } ( G ) = γ { 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 ∈ V ( G )$. The vertex set $V ( G )$ is the union of the sets ${ x }$ and $V ( G ) \ { x }$. Clearly, ${ x }$ is an independent set and $V ( G ) \ { 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 ∈ N$, then
(1)
$τ C k ( G ) = γ × k ( G ) = k$ for $k ≤ n$;
(2)
$τ C { k } ( G ) = γ { k } ( G ) = k$;
(3)
$τ C − ( G ) = γ − ( G ) = 1$;
(4)
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 $τ C s ( G ) = τ C − ( G ) = − 3$. However, $γ s ( G ) = γ − ( 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$3 p + 3 ℓ + 2$vertices. Let U, S, X, and Y be pairwise disjoint subsets of$V ( G )$such that$U = { u i ∣ 1 ≤ i ≤ p }$,$S = { s i ∣ 1 ≤ i ≤ ℓ }$,$X = { x i ∣ 1 ≤ i ≤ p + ℓ + 1 }$, and$Y = { y i ∣ 1 ≤ i ≤ p + ℓ + 1 }$. The graph G is an$H 1$-split graph if$V ( G ) = U ∪ S ∪ X ∪ Y$and G entirely satisfies the following three conditions.
(1)
$I = S ∪ Y$ and $C = U ∪ X$.
(2)
$N G ( y i ) = { x i }$ for $1 ≤ i ≤ p + ℓ + 1$.
(3)
$| N G ( s i ) ∩ U | = 3$ and $N G ( s i ) ∩ X = { x i }$ for $1 ≤ i ≤ ℓ$.
Theorem 6.
For any $H 1$-split graph $G = ( I , C , E )$, $τ C s ( G ) = γ s ( G )$ and $τ C − ( G ) = γ − ( G )$.
Proof.
We first prove $τ C s ( G ) = γ s ( G )$. Let $G = ( I , C , E )$ be an $H 1$-split graph. As stated in Definition 9, I can be partitioned into $S = { s i ∣ 1 ≤ i ≤ ℓ }$ and $Y = { y i ∣ 1 ≤ i ≤ p + ℓ + 1 }$, and C can be partitioned into $U = { u i ∣ 1 ≤ i ≤ p }$ and $X = { x i ∣ 1 ≤ i ≤ p + ℓ + 1 }$. Assume that f is a minimum-weight SDF of G. For each $y i ∈ Y$, $| N G [ y i ] | = 2$ and $y i$ is adjacent to only the vertex $x i ∈ X$. Then, $f ( x i ) = f ( y i ) = 1$ for $1 ≤ i ≤ p + ℓ + 1$. Since $C = U ∪ X$ and $| U | = p$, we know that $f ( C ) = f ( U ) + f ( X ) ≥ ( − p ) + ( p + ℓ + 1 ) ≥ ℓ + 1$. Notice that $f ( N G [ y ] ) ≥ 1$ and $N G [ y ] ∈ C ( G )$ for every $y ∈ I$. Therefore, f is also an SCTF of G. We have $τ C s ( G ) ≤ γ s ( G )$.
Assume that h is a minimum-weight SCTF of G. For each $y i ∈ Y$, $| N G [ y i ] | = 2$ and $y i$ is adjacent to only the vertex $x i ∈ X$. Then, $h ( x i ) = h ( y i ) = 1$ for $1 ≤ i ≤ p + ℓ + 1$. Consider the vertices in I. Since $N G [ y ] ∈ C ( G )$ for every $y ∈ I$, $h ( N G [ y ] ) ≥ 1$. We now consider the vertices in C. Recall that $C = U ∪ X$. Let $u i ∈ U$. Since $| U | = p$ and $| S | = ℓ$, we know that $h ( N G [ u i ] ) = h ( U ) + h ( X ) + h ( N G [ u i ] ∩ S ) ≥ ( − p ) + ( p + ℓ + 1 ) + ( − ℓ ) ≥ 1$. Let $x i ∈ X$. Then, $h ( N G [ x i ] ) = h ( U ) + h ( X ) + h ( y i ) + h ( s i ) ≥ ( − p ) + ( p + ℓ + 1 ) + 1 − 1 ≥ ℓ + 1$. Therefore, h is also an SDF of G. We have $γ s ( G ) ≤ τ C s ( G )$.
Following what we have discussed above, we have $τ C s ( G ) = γ s ( G )$. The proof for $τ C − ( G ) = γ − ( G )$ is analogous to that for $τ C s ( G ) = γ s ( G )$. Hence, the theorem holds for any $H 1$-split graphs. □
Theorem 7.
The SDP on $H 1$-split graphs is NP-complete.
Proof.
We reduce the (3,2)-hitting set problem to the SDP on $H 1$-split graphs. Let $U = { u i ∣ 1 ≤ i ≤ p }$ and let $C = { C 1 , C 2 , … , C ℓ }$ such that $C i ⊆ U$ and $| C i | = 3$ for $1 ≤ i ≤ ℓ$. A (3,2)-hitting set for the instance $( U , C )$ is a subset $U ′$ of U such that $| C i ∩ U ′ | ≥ 2$ for $1 ≤ i ≤ ℓ$. The (3,2)-hitting set problem is to find a minimum (3,2)-hitting set for any instance $( U , C )$. The (3,2)-hitting set problem is NP-complete [17].
Consider an instance $( U , C )$ of the (3,2)-hitting set problem. Let $S = { s i ∣ 1 ≤ i ≤ ℓ }$, $X = { x i ∣ 1 ≤ i ≤ p + ℓ + 1 }$, and $Y = { y i ∣ 1 ≤ i ≤ p + ℓ + 1 }$. We construct an $H 1$-split graph $G = ( I , C , E )$ by the following steps.
(1)
Let $I = S ∪ Y$ be an independent set and let $C = U ∪ X$ be a clique.
(2)
For each vertex $s i ∈ S$, a vertex $u ∈ U$ is connected to $s i$ if $u ∈ C i$.
(3)
For $1 ≤ i ≤ p + ℓ + 1$, the vertex $y i$ is connected to the vertex $x i$.
(4)
For $1 ≤ i ≤ ℓ$, the vertex $s i$ is connected to the vertex $x i$.
Let $τ h ( 3 , 2 )$ be the minimum cardinality of a (3,2)-hitting set for the instance $( U , C )$. Assume that $U ′$ is a minimum (3,2)-hitting set for the instance $( U , C )$. Then, $| U ′ | = τ h ( 3 , 2 )$. Let f be a function whose domain is $V ( G )$ and range is ${ − 1 , 1 }$, and $f ( v ) = 1$ if $v ∈ X ∪ Y ∪ U ′$ and $f ( v ) = − 1$ if $v ∈ S ∪ ( U \ U ′ )$. Clearly, f is an SDF of G. We have $γ s ( G ) ≤ 2 ( p + ℓ + 1 ) + | U ′ | − ℓ − ( p − | U ′ | ) = p + ℓ + 2 τ h ( 3 , 2 ) + 2$.
Assume that f is minimum-weight SDF of G. For each $y i ∈ Y$, $| N G [ y i ] | = 2$ and $y i$ is adjacent to only the vertex $x i ∈ X$. Then, $f ( x i ) = f ( y i ) = 1$ for $1 ≤ i ≤ p + ℓ + 1$. For any vertex $v ∈ X ∪ Y ∪ U$, $f ( N G [ v ] ) ≥ 1$ no matter what values the function f assigns to the vertices in U or in S. Consider the vertices in S. By the construction of G, $d e g G ( s i ) = 4$ and $| N G [ s i ] | = 5$ for $1 ≤ i ≤ ℓ$. There are at least three vertices in $N G [ s i ]$ with the function value 1. If $f ( N G [ s i ] ) = 5$, then there exists an SDF g of G such that $g ( s i ) = − 1$ and $g ( v ) = f ( v )$ for every $v ∈ V ( G ) \ { s i }$. Then, $g ( V ( G ) ) < f ( V ( G ) )$. It contradicts the assumption that the weight of f is minimum. Therefore, there exists a minimum-weight SDF h of G such that $h ( s i ) = − 1$ for $1 ≤ i ≤ ℓ$. Notice that $N G ( s i ) = C i ∪ { x i }$ for $1 ≤ i ≤ ℓ$. There are at least two vertices in $C i$ with the function value 1. Then, the set $U ′ = { u ∈ U ∣ h ( u ) = 1 }$ is a (3,2)-hitting set for the instance $( U , C )$. We have $p + ℓ + 2 τ h ( 3 , 2 ) + 2 ≤ p + ℓ + 2 | U ′ | + 2 = γ s ( G )$.
Following what we have discussed above, we know that $γ s ( G ) = p + ℓ + 2 τ h ( 3 , 2 ) + 2$. Hence, the SDP on $H 1$-split graphs is NP-complete. □
Corollary 4.
The SCTP and the MCTP on split graphs are NP-complete.
Proof.
The corollary holds by Theorems 6 and 7 and the NP-completeness of the MDP on split graphs [17]. □

## 5. Doubly Chordal and Dually Chordal Graphs

Assume that G is a graph with n vertices $x 1 , x 2 , … , x n$. Let $i ∈ { 1 , 2 , … , n }$ and let $G i$ be the subgraph $G [ V ( G ) \ { x 1 , x 2 , … x i − 1 } ]$. For every $x ∈ V ( G i )$, let $N i [ x ] = { y ∣ y ∈ ( N G [ x ] \ { x 1 , x 2 , … , x i − 1 } ) }$. In $G i$, if there exists a vertex $x j ∈ N i [ x i ]$ such that $N i [ x k ] ⊆ N i [ x j ]$ for every $x k ∈ N i [ x i ]$, then the ordering $( x 1 , x 2 , … , 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, $τ C ( G ) = α C ( G )$, but G is not necessarily clique perfect or chordal.
Proof.
Brandstädt 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, $τ C ( G ) = α 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, $τ C ( H ) = α C ( H ) = 1$, but $τ C ( C 4 ) = 2$ and $α C ( C 4 ) = 1$. Hence, a dually chordal graph is not necessarily clique perfect or chordal. □
Theorem 8.
Suppose that $k ∈ 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 ) ∪ { x }$ and $E ( H ) = E ( G ) ∪ { ( x , y ) ∣ y ∈ 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 ∪ { x }$ is a k-FCTS of H. Then $τ C k ( H ) ≤ τ C k − 1 ( G ) + 1$.
By contradiction, we can verify that there exists a minimum k-FCTS D of H such that $x ∈ D$. Let $S = D \ { x }$. Clearly, S is a $( k − 1 )$-FCTS of G. Then $τ C k − 1 ( G ) ≤ τ C k ( H ) − 1$. Following what we have discussed above, we have $τ C k ( H ) = τ C k − 1 ( G ) + 1$. Notice that $τ C ( G ) = τ 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, $τ 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. □

## 6. k-Trees

Assume that G is a graph with n vertices $x 1 , x 2 , … , x n$. Let $i ∈ { 1 , 2 , … , n }$ and let $G i$ be the subgraph $G [ V ( G ) \ { x 1 , x 2 , … x i − 1 } ]$. For every $x ∈ V ( G i )$, let $N i [ x ] = { y ∣ y ∈ ( N G [ x ] \ { x 1 , x 2 , … , x i − 1 } ) }$. If $N i [ x i ]$ is a clique for $1 ≤ i ≤ n$, then the ordering $( x 1 , x 2 , … , x n )$ is a perfect elimination ordering (abbreviated as PEO) of G. A graph G is chordal if and only if G has a PEO [26]. A chordal graph G is a k-tree if and only if either G is a complete graph of k vertices or G has more than k vertices and there exists a PEO $( x 1 , x 2 , … , x n )$ such that $N i [ x i ]$ is a clique of k vertices if $i = n − k + 1$; otherwise, $N i [ x i ]$ is a clique of $k + 1$ vertices for $1 ≤ i ≤ n − k$. Figure 4 shows a 2-tree with the PEO $( v 1 , v 2 , … , v 13 )$.
In [3], Chang et al. showed that the MCTP is NP-complete for k-trees with unbounded k by proving $γ ( G ) = τ M ( G )$ for any k-tree G. However, Figure 4 shows a counterexample that disproves $γ ( G ) = τ M ( G )$ for any k-tree G. The graph H in Figure 4 is a 2-tree with the perfect elimination ordering $( v 1 , v 2 , … , v 13 )$. The set ${ v 5 , v 10 }$ is the minimum dominating set of H and the set ${ v 5 , v 10 , v 11 }$ is a minimum MCTS of H. A modified NP-completeness proof is therefore desired for the MCTP on k-tree with unbounded k.
Theorem 10.
The MCTP and the MCIP are NP-complete for k-trees with unbounded k.
Proof.
The CTP and the CIP are NP-complete for k-trees with unbounded k [8]. Since every maximal clique in a k-tree is also a maximum clique [27], an MCTS is a CTS and an MCIS is a CIS. Hence, the MCTP and the MCIP are NP-complete for k-trees with unbounded k. □
Theorem 11.
The SCTP is NP-complete for k-trees with unbounded k.
Proof.
Suppose that $k 1 ∈ N$ and G is a $k 1$-tree with $| V ( G ) | > k 1$. Let $C ( G ) = { C 1 , C 2 , … , C ℓ }$. Since G is a $k 1$-tree, $| C i | = k 1 + 1$ for $1 ≤ i ≤ ℓ$.
Let Q be a clique with $k 1 + 1$ vertices. Let H be a graph such that $V ( H ) = V ( G ) ∪ Q$ and $E ( H ) = E ( G ) ∪ { ( x , y ) ∣ x , y ∈ Q } ∪ { ( x , y ) ∣ x ∈ Q , y ∈ V ( G ) }$. Let $X i = C i ∪ Q$ be a clique for $1 ≤ i ≤ ℓ$. Clearly, $C ( H ) = { X i ∣ 1 ≤ i ≤ ℓ }$. Let $k 2 = 2 k 1 + 1$. Then, H is a $k 2$-tree and $| X i | = k 2 + 1 = 2 k 1 + 2$ for $1 ≤ i ≤ ℓ$. Clearly, we can verify that there exists a minimum-weight SCTF h of H of such that $h ( x ) = 1$ for every $x ∈ Q$. Then, $C i = X i \ Q$ contains at least one vertex x with $h ( x ) = 1$ for $1 ≤ i ≤ ℓ$. Let $S = { x ∣ x ∈ V ( H ) \ Q$ and $h ( x ) = 1 }$. Then, S is a CTS of G. Since $τ C s ( H ) = | Q | + 2 | S | − | V ( G ) |$, we have $| Q | + 2 τ C ( G ) − | V ( G ) | ≤ τ C s ( H )$.
Assume that D is a minimum CTS of G. Let f be a function of H whose domain is $V ( H )$ and range is ${ − 1 , 1 }$, and (1) $f ( x ) = 1$ for every $x ∈ Q$, (2) $f ( x ) = 1$ for every $x ∈ D$, and (3) $f ( x ) = − 1$ for every $x ∈ V ( G ) \ D$. Each maximal clique of H has at least $k 1 + 2$ vertices with the function value 1. Therefore, f is an SCTF. We have $τ C s ( H ) ≤ | Q | + 2 τ C ( G ) − | V ( G ) |$. Following what we have discussed above, we know that $τ C s ( H ) = | Q | + 2 τ C ( G ) − | V ( G ) |$. The theorem therefore holds by the NP-completeness of the CTP for k-trees [8]. □
Theorem 12.
Suppose that $κ ∈ N$ the κ-FCTP is NP-complete on k-trees with unbounded k.
Proof.
Assume that $k 1 ∈ N$ and G is a $k 1$-tree with $| V ( G ) | > k 1$. Let H be a graph such that $V ( H ) = V ( G ) ∪ { x }$ and $E ( H ) = E ( G ) ∪ { ( x , y ) ∣ y ∈ V ( G ) }$. Clearly, H is a $( k 1 + 1 )$-tree and we can construct H in linear time. Following the argument analogous to the proof of Theorem 8, we have $τ C κ ( H ) = τ C κ − 1 ( G ) + 1$. The theorem therefore holds by the NP-completeness of the CTP for k-trees [8]. □
Theorem 13.
The SCTP and κ-FCTP problems can be solved in linear-time for k-trees with fixed k.
Proof.
Assume that $κ ∈ N$ and G is a graph. The $κ$-FCTP is the GCTP with the CSRF R whose domain is $C ( G )$ and range is ${ κ }$. By Lemma 5, $τ C s ( G )$ can be obtained from the solution to the GCTP on a graph G with a particular CSRF R. Since the GCTP is linear-time solvable for k-trees with fixed k [8], the SCTP and $κ$-FCTP are also linear-time solvable for k-trees with fixed k. □

## 7. Planar, Total, and Line Graphs

In a graph, a vertex x and an edge e are incident to each other if e connects x to another vertex. Two edges are adjacent if they share a vertex in common. Let G and H be graphs such that each vertex $x ∈ V ( H )$ corresponds to an edge $e x ∈ E ( G )$ and two vertices $x , y ∈ V ( H )$ are adjacent in H if and only if their corresponding edges $e x$ and $e y$ are adjacent in G. Then, H is the line graph of G and denoted by $L ( G )$. Let $H ′$ be a graph such that $V ( H ′ ) = V ( G ) ∪ E ( G )$ and two vertices $x , y ∈ V ( H ′ )$ are adjacent in H if and only if x and y are adjacent or incident to each other in G. Then, $H ′$ is the total graph of G and denoted by $T ( G )$.
Lemma 9
([28]). The following statements hold for any triangle-free graph G.
(1)
Every maximal clique of $L ( G )$ is the set of edges of G incident to some vertex of G.
(1)
Two maximal cliques in $L ( G )$ intersect if and only if their corresponding vertices (in G) are adjacent in G.
Theorem 14.
The MCIP is NP-complete for any 4-regular planar graph G with the clique number 3.
Proof.
Since $| C ( G ) | = O ( n )$ for any planar graph G [29], the MCIP on planar graphs is in NP. Let $G$ be the class of triangle-free, 3-connected, cubic planar graphs. The independent set problem remains NP-complete even when restricted to the graph class $G$ [30]. We reduce this NP-complete problem to the MCIP for 4-regular planar graphs with the clique number 3 as follows.
Let $G ∈ G$ and $H = L ( G )$. Clearly, we can construct H in polynomial time. By Lemma 9, we know that H is a 4-regular planar graph with $ω ( H ) = 3$ and each maximal clique is a triangle in H.
Assume that $D = { x 1 , x 2 , … , x ℓ }$ is an independent set of G of maximum cardinality. Since $G ∈ G$, $d e g G ( x ) = 3$ for every $x ∈ V ( G )$. Let $e i 1 , e i 2 , e i 3 ∈ E ( G )$ have the vertex $x i$ in common for $1 ≤ i ≤ ℓ$. Then, $e i 1 , e i 2 , e i 3$ form a triangle in H. Let $C i$ be the triangle formed by $e i 1 , e i 2 , e i 3$ in H for $1 ≤ i ≤ ℓ$. For each pair of vertices $x j , x k ∈ D$, $x j$ is not adjacent to $x k$ in G. Therefore, $C j$ and $C k$ in H do not intersect. The set ${ C 1 , C 2 , … , C ℓ }$ is an MCIS of H. We have $α ( G ) ≤ α M ( H )$.
Assume that $S = { C 1 , C 2 , … , C ℓ }$ is a maximum MCIS of H. Then, each $C i ∈ S$ is a triangle in H. Let $C i$ be formed by $e i 1 , e i 2 , e i 3$ in H for $1 ≤ i ≤ ℓ$. Then, $e i 1 , e i 2 , e i 3$ are incident to the same vertex in G. For $1 ≤ i ≤ ℓ$, let $e i 1 , e i 2 , e i 3 ∈ E ( G )$ have the vertex $x i$ in common. For each pair of $C j , C k ∈ S$, $C j$ and $C k$ do not intersect. Therefore, $x j$ is not adjacent to $x k$ in G. The set ${ x 1 , x 2 , … , x ℓ }$ is an independent set of G. We have $α M ( H ) ≤ α ( G )$.
Hence, $α ( G ) = α M ( H )$. For $k ∈ N$, we know that $α ( G ) ≥ k$ if and only if $α M ( G ) ≥ k$. □
Corollary 5.
The MCIP is NP-complete for line graphs of triangle-free, 3-connected, cubic planar graphs.
Proof.
The corollary holds by the reduction of Theorem 14. □
Theorem 15.
The MCIP problem is NP-complete for total graphs of triangle-free, 3-connected, cubic planar graphs.
Proof.
Since $| C ( G ) | = O ( n )$ for a planar graph G, the MCIP on planar graphs is in NP. Let $G$ be the classes of traingle-free, 3-connected, cubic planar graphs. The independent set problem remains NP-complete even when restricted to the graph class $G$ [30]. We reduce this NP-complete problem to MCIP for for total graphs of triangle-free, 3-connected, cubic planar graphs. as follows
Let $G ∈ G$ and $H = T ( G )$. Clearly, we can construct H in polynomial time. By Lemma 9, we can verify that H is a 6-regular graph with $ω ( H ) = 4$.
Assume that $D = { x 1 , x 2 , … , x ℓ }$ is an independent set of G of maximum cardinality. Since $G ∈ G$, $d e g G ( x ) = 3$ for every $x ∈ V ( G )$. Let $e i 1 , e i 2 , e i 3 ∈ E ( G )$ have the vertex $x i$ in common. Then, $x i , e i 1 , e i 2 , e i 3$ form a maximum clique in H. Let $C i$ be the maximum clique formed by $x i , e i 1 , e i 2 , e i 3$ in H for $1 ≤ i ≤ ℓ$. For each pair of vertices $x j , x k ∈ D$, $x j$ is not adjacent to $x k$ in G. Therefore, $C j$ and $C k$ in H do not intersect. The set ${ C 1 , C 2 , … , C ℓ }$ is an MCIS of H. We have $α ( G ) ≤ α M ( H )$.
Assume that $S = { C 1 , C 2 , … , C ℓ }$ is a maximum MCIS of H. By the construction of H, each $C i ∈ S$ is formed by three edge-vertices in $E ( G )$ and their common end vertex in $V ( G )$. Let $x i ∈ V$ and $e i 1 , e i 2 , e i 3 ∈ E ( G )$ in H such that $C i$ is formed by $v i , e i 1 , e i 2 , e i 3$ for $1 ≤ i ≤ ℓ$. For each pair of $C j , C k ∈ C$, $C j$ and $C k$ do not intersect. Therefore, $x j$ is not adjacent to $x k$ in G. The set ${ x 1 , x 2 , … , x ℓ }$ is an independent set of G. We have $α M ( H ) ≤ α ( G )$.
Hence, $α ( G ) = α M ( H )$. For $k ∈ N$, we know that $α ( G ) ≥ k$ if and only if $α M ( H ) ≥ k$. □

## Funding

This research is supported by a Taiwanese grant under Grant No. NSC-97-2218-E-130-002-MY2.

## Acknowledgments

We are grateful to the anonymous referees for their valuable comments and suggestions to improve the presentation of this paper.

## Conflicts of Interest

The author declares no conflict of interest

## References

1. Dahlhaus, E.; Kratochvíl, J.; Manuel, P.D.; Miller, M. Transversal partitioning in balanced hypergraphs. Discret. Math. 1997, 79, 75–89. [Google Scholar] [CrossRef]
2. Dahlhaus, E.; Manuel, P.D.; Miller, M. Maximum h-colourable subgraph problem in balanced graphs. Inf. Process. Lett. 1998, 65, 301–303. [Google Scholar] [CrossRef]
3. Chang, M.-S.; Kloks, T.; Lee, C.-M. Maximum clique transversals. In Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, Boltenhagen, Germany, 14–16 June 2001; Lecture Notes in Computer Science. Springer: Berlin/Heidelberg, Germany, 2001; Volume 2204, pp. 32–43. [Google Scholar]
4. Lee, C.-M. Variations of maximum-clique transversal sets on graphs. Ann. Oper. Res. 2010, 181, 21–66. [Google Scholar] [CrossRef]
5. Lee, C.-M.; Chang, M.-S. Signed and minus clique-transversal function on graphs. Inf. Process. Lett. 2009, 109, 414–417. [Google Scholar] [CrossRef]
6. Wang, H.; Kang, L.; Shan, E. Signed clique-transversal functions in graphs. Int. J. Comput. Math. 2010, 87, 2398–2407. [Google Scholar] [CrossRef]
7. Xu, G.; Shan, E.; Kang, L.; Chang, T.C.E. The algorithmic complexity of the minus clique-transversal problem. Appl. Math. Comput. 2007, 189, 1410–1418. [Google Scholar]
8. Chang, M.S.; Chen, Y.H.; Chang, G.J.; Yan, J.H. Algorithmic aspects of the generalized clique transversal problem on chordal graphs. Discret. Appl. Math. 1996, 66, 189–203. [Google Scholar]
9. Lee, C.-M.; Chang, M.-S. Variations of Y-dominating functions on graphs. Discret. Math. 2008, 308, 4185–4204. [Google Scholar] [CrossRef]
10. Balachandran, V.; Nagavamsi, P.; Rangan, C.P. Clique transversal and clique independence on comparability graphs. Inf. Process. Lett. 1996, 58, 181–184. [Google Scholar] [CrossRef]
11. Lee, C.-M.; Chang, M.-S. Distance-hereditary graphs are clique-perfect. Discret. Appl. Math. 2006, 154, 525–536. [Google Scholar] [CrossRef]
12. Bonomo, F.; Durán, G.; Lin, M.C.; Szwarcfiter, J.L. On balanced graphs. Math. Program. 2006, 105, 233–250. [Google Scholar] [CrossRef]
13. Lehel, J.; Tuza, Z. Neighborhood perfect graphs. Discret. Math. 1986, 61, 93–101. [Google Scholar] [CrossRef]
14. Chang, G.J.; Farber, M.; Tuza, Z. Algorithmic aspects of neighborhood numbers. SIAM J. Discret. Math. 1993, 6, 24–29. [Google Scholar] [CrossRef]
15. Fulkerson, D.R.; Hoffman, A.; Oppnheim, R. On balnaced matrices. Math. Program. Study 1974, 1, 120–132. [Google Scholar]
16. Argiroffo, G.; Leoni, V.; Torres, P. On the complexity of {k}-domination and k-tuple domination in graphs. Inf. Process. Lett. 2015, 115, 556–561. [Google Scholar] [CrossRef]
17. Faria, L.; Hon, W.-K.; Kloks, T.; Liu, H.-H.; Wang, T.-M.; Wang, Y.-L. On complexities of minus domination. Discret. Optim. 2016, 22, 6–19. [Google Scholar] [CrossRef]
18. Liao, C.-S.; Chang, G.J. k-tuple domination in graphs. Inf. Process. Lett. 2003, 87, 45–50. [Google Scholar] [CrossRef]
19. Brandstädt, A.; Le, V.B.; Spinrad, J.P. Graph Classes–A Survey, SIAM Monographs on Discrete Math and Applications; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 1999. [Google Scholar]
20. Fulkerson, D.R.; Gross, O. Incidence matrices and interval graphs. Pac. J. Math. 1965, 15, 835–855. [Google Scholar] [CrossRef]
21. Brandstädt, A.; Dragan, F.F.; Chepoi, V.D.; Voloshin, V.I. Dually chordal graphs. SIAM J. Discret. Math. 1998, 11, 437–455. [Google Scholar] [CrossRef]
22. Dragan, F.F. HT-graphs: Centers, connected r-domination, and Steiner trees. Comput. Sci. J. Mold. 1993, 1, 64–83. [Google Scholar]
23. Moscarini, M. Doubly chordal graphs, Steiner trees, and connected domination. Networks 1993, 23, 59–69. [Google Scholar] [CrossRef]
24. Prisner, E.; Szwarcfiter, J.L. Recognizing clique graphs of directed and rooted path graphs. Discret. Appl. Math. 1999, 94, 321–328. [Google Scholar] [CrossRef]
25. Brandstädt, A.; Chepoi, V.D.; Dragan, F.F. Clique r-domination and clique r-packing problems on dually chordal graphs. SIAM J. Discret. Math. 1997, 10, 109–127. [Google Scholar] [CrossRef]
26. Rose, D.J. Triangulated graphs and the elimination process. J. Math. Anal. Appl. 1970, 32, 597–609. [Google Scholar] [CrossRef]
27. Patil, H.P. On the structure of k-trees. J. Comb. Inf. Syst. Sci. 1986, 11, 57–64. [Google Scholar]
28. Guruswami, V.; Rangan, C.P. Algorithmic aspects of clique-transversal and clique-independent sets. Discret. Appl. Math. 2000, 100, 183–202. [Google Scholar] [CrossRef]
29. Wood, D.R. On the maximum number of cliques in a graph. Graphs Comb. 2007, 23, 337–352. [Google Scholar] [CrossRef]
30. Uehara, R. NP-Complete Problems on a 3-Connected Cubic Planar Graph and Their Applications; Technical Report TWCU-M-0004; Tokyo Woman’s Christian University: Tokyo, Japan, 1996. [Google Scholar]
Figure 1. (a) The sun $S 3$. (b) A sun $S 4$.
Figure 1. (a) The sun $S 3$. (b) A sun $S 4$.
Figure 2. A split graph G with $τ C s ( G ) = τ C − ( G ) = − 3$.
Figure 2. A split graph G with $τ C s ( G ) = τ C − ( G ) = − 3$.
Figure 3. A split graph G with one of its partitions indicated.
Figure 3. A split graph G with one of its partitions indicated.
Figure 4. A 2-tree H.
Figure 4. A 2-tree H.
 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.