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
(This article belongs to the Special Issue Graph Algorithms and Applications)

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.
Keywords: clique independent set; clique transversal number; signed clique transversal function; minus clique transversal function; k-fold clique transversal set clique independent set; clique transversal number; signed clique transversal function; minus clique transversal function; k-fold clique transversal set

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:
minimize i = 1 n x i subject   to M X C
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)
τ C s ( G ) = γ s ( G ) = 1 i f   n   i s   o d d ; 2 o t h e r w i s e .
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 .
Algorithms 14 00022 g001
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 .
Algorithms 14 00022 g002
Figure 3. A split graph G with one of its partitions indicated.
Figure 3. A split graph G with one of its partitions indicated.
Algorithms 14 00022 g003
Figure 4. A 2-tree H.
Figure 4. A 2-tree H.
Algorithms 14 00022 g004
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Back to TopTop