On Balanced Graphs

Mathematical Programming manuscript No. (will be inserted by the editor) Flavia Bonomo · Guillermo Durán · Min Chih Lin · Jayme L Szwarcfiter On Balanced Graphs Received: date / Accepted: date Abstract Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and cliquetransversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. Keywords algorithms · balanced graphs · balanced hypergraphs · clique graphs · domination · 0-1 matrices Mathematics Subject Classification (2000) 05C50 · 05C17 · 05C85 Flavia Bonomo, Min Chih Lin Dep. de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina. E-mail: {fbonomo,oscarlin}@dc.uba.ar Guillermo Durán Dep. de Ingenierı́a Industrial, Facultad de Ciencias Fı́sicas y Matemáticas, Universidad de Chile, Santiago, Chile. E-mail: gduran@dii.uchile.cl Jayme L Szwarcfiter Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brasil. E-mail: jayme@nce.ufrj.br 2 Flavia Bonomo et al. 1 Introduction A clique in a graph is a complete subgraph maximal with respect to inclusion. The clique number of a graph G is the cardinality of a maximum clique of G and is denoted by ω(G). The chromatic number of a graph G is the smallest number of colours that can be assigned to the vertices of G in such a way that no two adjacent vertices receive the same colour. An obvious lower bound is the clique number of G. Berge [2] called a graph G perfect whenever the chromatic number of every induced subgraph H of G is equal to ω(H). Perfect graphs are very interesting from an algorithmic point of view. While determining the clique number and the chromatic number of a graph are NP-complete problems, they are solvable in polynomial time for perfect graphs [19]. For more background information on algorithms on perfect graphs see [18]. A sequence v1 , . . . , vk of distinct vertices (k ≥ 3) is a cycle in a graph G if (v1 , v2 ), . . . , (vk−1 , vk ), (vk , v1 ) are edges of G. These edges are called the edges of the cycle. The length of the cycle is the number k of its edges. An odd cycle is a cycle of odd length. In subsequent expressions concerning cycles, all index arithmetic is done modulo the length of the cycle. A chord of a cycle is an edge between two vertices of the cycle that is not an edge of the cycle. A cycle is chordless if it contains no chords. Chordless cycles of length greater than 3 are called holes. A sequence v1 , E1 , . . . , vk , Ek of distinct vertices v1 , . . . , vk and distinct hyperedges E1 , . . . , Ek of a hypergraph H is a special cycle of length k if k ≥ 3, vi , vi+1 ∈ Ei and Ei ∩ {v1 , . . . , vk } = {vi , vi+1 }, for each i, 1 ≤ i ≤ k. Let A be a 0-1 matrix. We say that the row i is included in the row k if for every column j, A(i, j) = 1 implies A(k, j) = 1. Let M1 , . . . , Mk and v1 , . . . , vn be the cliques and vertices of a graph G, respectively. We define AG , a clique matrix of G, as a 0-1 matrix whose entry (i, j) is 1 if vj ∈ Mi , and 0 otherwise. A 0-1 matrix M is balanced if it does not contain the vertex-edge incidence matrix of an odd cycle as a submatrix. A 0-1 matrix M is totally balanced if it does not contain the vertex-edge incidence matrix of a cycle as a submatrix. In 1969 (c.f. [14]), Berge defined a hypergraph to be balanced if its incidence matrix is balanced, or equivalently, if it contains no special cycles of odd length. See [3,4]. Applying this concept to graphs, one obtains the class of balanced graphs, formed by those graphs having a balanced clique matrix. Note that balanced graphs are well defined, since if the clique matrix of a graph is balanced then all its clique matrices are balanced. Balanced graphs were considered in [13]. The clique hypergraph of a graph G has the same vertex set as G and all cliques of G as hyperedges. Clearly, a graph G is balanced if and only if its clique hypergraph is balanced. Let v, w be vertices of G. Denote by M (G) the set of cliques of G, by M (v) the set of cliques of G that contain v, and by M (v, w) the set of cliques of G that contain v and w. Vertices that belong to exactly one clique will be called simplicial vertices. On Balanced Graphs 3 The neighborhood of a vertex v in a graph G is the set NG (v) consisting of all the vertices that are adjacent to v. The closed neighborhood of v is NG [v] = NG (v) ∪ {v}. The common neighborhood and the closed common neighborhood of an edge e = (v, w) are NG (e) = NG (v) ∩ NG (w) and NG [e] = NG [v]∩NG [w], respectively, and, in a more general way, the common neighborhood and the closed common neighborhood of a non T empty subset T of vertices W are NG (W ) = w∈W NG (w) and NG [W ] = w∈W NG [w], respectively. We define NG (∅) = NG [∅] = V (G). A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. A clique-independent set is a subset of pairwise disjoint cliques of G. Denote by τc (G) and αc (G) the cardinalities of the minimum clique-transversal and maximum clique-independent set of G, respectively. A graph G is clique-perfect when τc (H) = αc (H), for every induced subgraph H of G [20]. A family of subsets satisfies the Helly property when every subfamily of it consisting of pairwise intersecting subsets has a common element. A graph is clique-Helly when its cliques satisfy the Helly property. A graph is hereditary clique-Helly (HCH) when H is clique-Helly for every induced subgraph H of G. Consider a finite family of non-empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The clique graph K(G) of G is the intersection graph of the cliques of G. We can define K j (G) as the j-th iterated clique graph of G, where K 1 (G) = K(G) and K j (G) = K(K j−1 (G)), j ≥ 2. Let H be a class of graphs. The notation K(H) means the class of clique graphs of the graphs in H, and K −1 (H) the class of graphs whose clique graphs are in H. Let C be a set of cliques of G. The clique subgraph of a graph G generated by C is the graph formed by the vertices and edges of C. A clique subgraph of G is not necessarily an induced subgraph of G. A graph G is an interval graph if G is the intersection graph of a finite family of intervals of the real line. A graph G is trivially perfect if for all induced subgraphs H of G, the cardinality of the maximum stable set of H is equal to the number of cliques of H. A 0-1 matrix M is totally unimodular if the determinant of each square submatrix of M is 0, 1 or -1. A graph G is totally unimodular if its clique matrix is totally unimodular. Since the determinant of the vertex-edge incidence matrix of an odd cycle is ±2, totally unimodular matrices are balanced matrices and then totally unimodular graphs are balanced graphs. Interval graphs and trivially perfect graphs are totally unimodular graphs [18] and, therefore, they are balanced graphs. A graph is bipartite when it contains no cycles of odd length. A graph is strongly chordal when it is chordal and each of its cycles of even length at least 6 has an odd chord [16]. Such a class corresponds exactly to totally balanced graphs, i.e., graphs whose clique matrices are totally balanced [1]. 4 Flavia Bonomo et al. Bipartite graphs and strongly chordal graphs form important subclasses of balanced graphs. The organization of the paper is the following. In Section 2, we describe background properties of balanced graphs. In Section 3, new characterizations of balanced graphs are presented. One of them is by forbidden subgraphs and the other is by clique subgraphs. In Section 4, four subclasses of balanced graphs are introduced using simple properties of domination. We analyse the inclusion relations between them. Two of these classes are characterized using 0-1 matrices and the characterizations lead to polynomial recognition algorithms. In the final part of this section, we present a combinatorial algorithm for the maximum stable set problem for one of these subclasses. Finally, in the last section, we study the clique graphs of balanced graphs and these four subclasses. As a corollary of these results, we deduce the existence of combinatorial algorithms for the maximum clique-independent set and the minimum clique-transversal problems for one of these subclasses of balanced graphs. 2 Preliminaries A characterization of hereditary clique-Helly graphs can be formulated in the following way: Theorem 1 [26] A graph G is hereditary clique-Helly if and only if AG does not contain a vertex-edge incidence matrix of a 3-cycle as a submatrix. This theorem implies the following result. Corollary 1 Let G be a balanced graph. Then G is hereditary clique-Helly. In [26], it is also proved that no connected hereditary clique-Helly graph has more cliques than edges. Then this result holds. Corollary 2 Let G be a connected balanced graph. Then the number of cliques of G is at most the number of edges of G. There exists an algorithm which calculates all the cliques of a graph in O(mnk) time where m is the number of edges, n the number of vertices and k the number of cliques [30] (the algorithm generates each clique sequentially in O(mn) time). So a clique matrix of a hereditary clique-Helly graph can be computed in polynomial time in the size of the graph. On the other hand, Conforti, Cornuéjols, and Rao formulated a polynomial-time recognition algorithm for balanced 0-1 matrices [10]. These two algorithms and the fact that hereditary clique-Helly graphs have no more than m cliques imply the following result. Corollary 3 [13] There is a polynomial-time recognition algorithm for balanced graphs. On Balanced Graphs 5 It should be mentioned that clique matrices where characterized by P. C. Gilmore in the 60’s, c.f. [12]. It is not difficult to see that the clique matrix of a graph G and the clique matrix of an induced subgraph of G are related in the following way: Lemma 1 Let G be a graph and H an induced subgraph of G. Then AH is the submatrix of AG obtained by keeping the columns corresponding to the vertices of H and removing the included rows. On the other hand, for hereditary clique-Helly graphs, the clique matrix of a graph G and the clique matrix of a clique subgraph of G are related in the following way: Theorem 2 [26] Let G be a hereditary clique-Helly graph and S a subset of its cliques. Let H be the clique subgraph of G formed by the vertices and edges of S. Then AH is the submatrix of AG obtained by taking the rows corresponding to the cliques in S and the columns corresponding to the vertices of these cliques. Since a submatrix of a balanced matrix is also balanced, these results imply that balanced graphs are closed under induced subgraphs and clique subgraphs. Let ek be a vector with k 1’s. A matrix M ∈ Rk×n is perfect if the polyhedron P (M ) = {x/x ∈ Rn , M x ≤ ek , x ≥ 0} has only integer extrema. Fulkerson, Hoffman and Oppenheim [17] proved the following result which implies that balanced matrices are perfect matrices. Theorem 3 [17] If M is a balanced matrix, then the polyhedra P (M ) = {x/x ∈ Rn , M x ≤ ek , x ≥ 0} and Q(M ) = {x/x ∈ Rn , M x ≥ ek , x ≥ 0} have only integer extrema. On the other hand, Chvátal [8] proved the theorem below that connects perfect matrices with perfect graphs. Theorem 4 [8] A graph G is perfect if and only if its clique matrix is perfect. By Theorems 3 and 4, balanced graphs are perfect graphs. A 0-1 matrix A is k-colorable if there exists a k-coloring of its columns such that for every row i that has at least two 1s in columns corresponding to colors J and L, there are entries aij = ail = 1, where column j has color J and column l has color L. Berge proved the following theorem. Theorem 5 [5] A 0-1 matrix A is balanced if and only if every submatrix of A is k-colorable for every k. Based on the proof of Theorem 5 and using the bicoloring algorithm of Cameron and Edmonds [7], a balanced matrix can be efficiently k-colored [11]. Since it is not difficult to see that for a graph G a χ(G)-coloring of AG gives an χ(G)-coloring of G, and in a balanced graph G a χ(G)-coloring of 6 Flavia Bonomo et al. G is equivalent to a ω(G)-coloring of G and ω(G) can be easily calculated, so there exists a polynomial time combinatorial algorithm to find an optimal coloring of a balanced graph [9]. Berge and Las Vergnas proved in [6] a theorem about balanced hypergraphs which can be formulated in terms of graphs in the following way: Theorem 6 [6] If G is a balanced graph then τc (G) = αc (G). Corollary 4 Balanced graphs are clique-perfect. Moreover, the clique-transversal number τc (G) (and hence the clique-independence number αc (G)) of a balanced graph G can be determined polynomially by linear programming [13]. 3 New characterizations of balanced graphs In this section, two new characterizations of balanced graphs are presented. The first one, by forbidden subgraphs and the second one, by clique subgraphs. A sun (or trampoline) is a chordal graph G on 2r vertices whose vertex set can be partitioned into two sets, W = {w1 , . . . , wr } and U = {u1 , . . . , ur }, such that W is a stable set and for each i and j, wj is adjacent to ui if and only if i = j or i ≡ j + 1 (mod r). A sun is odd if r is odd. Some subclasses of balanced graphs are characterized by forbidden subgraphs. We can see that in the following two theorems. Theorem 7 [16] A graph is strongly chordal if and only if it is sun-free chordal. Theorem 8 [24] A graph is chordal and balanced if and only if it is odd sun-free chordal. An extended odd sun is an odd cycle C and a subset of pairwise adjacent vertices We ⊆ NG (e)\C for each edge e of C, such that NG (We )∩NG (e)∩C = ∅ and |We | ≤ |NG (e) ∩ C|. Clearly, odd suns are extended odd suns. The smallest extended odd sun is the Hajös graph (Figure 1). Fig. 1 Hajös graph. Other examples of extended odd suns appear in Figure 2. Note that the subsets We and Wf , corresponding to the edges e and f respectively, may overlap. On Balanced Graphs 7 w1 v7 e7 v6 e6 e1 e5 v5 e7 v6 v2 e6 v4 e3 e1 e5 e2 e4 v1 v7 v1 v5 w2 v3 w3 w5 w1 w2 v2 e2 e3 e4 v4 w3 v3 w4 Fig. 2 Two examples of graphs that are not balanced. In the first one, W e1 = We7 = {w1 }, We2 = {w2 }, We3 = {w3 } and We4 = We5 = We6 = ∅. In the second one, We1 = {w1 , w2 }, We2 = {w3 }, We3 = {w4 }, We4 = {w5 } and We5 = We6 = We7 = ∅. Theorem 9 A graph is balanced if and only if it does not contain an extended odd sun as an induced subgraph. Proof Let G be a graph. Suppose that G has the following extended odd sun: an odd cycle C = {v1 , . . . , v2k+1 } and a subset of pairwise adjacent vertices Wi ⊆ NG (ei ) \ C for each edge ei = (vi , vi+1 ) of C, such that NG (Wi ) ∩ NG (ei ) ∩ C = ∅. Let ei = (vi , vi+1 ) be an edge of C. Then {vi , vi+1 } ∪ Wi is contained in a clique Mi of G, and Mi ∩ C = {vi , vi+1 } because N (ei ) ∩ N (Wi ) ∩ C = ∅. Now, if we choose the rows of AG corresponding to M1 , . . . , M2k+1 and the columns of AG corresponding to v1 , . . . , v2k+1 , we have a vertex-edge incidence matrix of an odd cycle as a submatrix of AG . So, AG is not balanced, and thus G is not balanced. Conversely, suppose that G is not a balanced graph, and then AG is not a balanced matrix. So, we have the following submatrix A′ in AG , where M1 , . . . , M2k+1 are cliques of G and v1 , . . . , v2k+1 are vertices of G: M1 M2 M3 . . . M2k+1 v1 1 0 0 . . . 1 v2 1 1 0 . . . 0 v3 0 1 1 . . . 0 . . . v2k+1 ... 0 ... 0 ... 0 . . . . . . ... 1 Fig. 3 Vertex-edge incidence matrix of an odd cycle. Thus v1 , . . . , v2k+1 is an odd cycle C of G and Mi is a clique such that Mi ∩C = {vi , vi+1 }. Let ei be the edge (vi , vi+1 ). Then either NG (ei )∩C = ∅ and then we define Wi to be the empty set, or for each v ∈ NG (ei ) ∩ C there is a vertex w in Mi non-adjacent to v, and those vertices form a subset of pairwise adjacent vertices Wi ⊆ NG (ei )\C such that NG (Wi )∩NG (ei )∩C = ∅ and |Wi | ≤ |NG (ei ) ∩ C|. ⊔ ⊓ 8 Flavia Bonomo et al. Fig. 4 An extended odd sun which is not minimal. Remark 1 Extended odd suns are not necessarily minimal. The Hajös graph is an induced subgraph of the extended odd sun of Figure 4. Theorem 10 A graph G is balanced if and only if G is hereditary cliqueHelly and does not contain a clique subgraph with an odd hole. Proof ⇒) Let G be a balanced graph. By Corollary 1, G is HCH. Let H be a clique subgraph of G. Since balancedness is hereditary for clique subgraphs, H is balanced. Since induced subgraphs of G are also balanced, H can not contain an odd chordless cycle of length ≥ 5 as an induced subgraph. ⇐) Suppose that G is not a balanced graph, thus AG is not a balanced matrix. If AG contains the vertex-edge incidence matrix of a 3-cycle as a submatrix, then G is not HCH. Otherwise, G is HCH and AG contains the vertex-edge incidence matrix of an odd hole as a submatrix A′ (Figure 3, with k ≥ 2). Let H be the clique subgraph of G formed by the cliques of G corresponding to the rows of A′ , and let H ′ be the subgraph of H induced by the vertices corresponding to the columns of A′ (these vertices are vertices of H by the construction of A′ ). By Theorem 2, the clique matrix AH is the submatrix of AG obtained by keeping the rows of A′ and then removing the null columns. Now, by Lemma 1, the clique matrix AH ′ is A′ . Thus H ′ is an odd hole. ⊔ ⊓ 4 Graph Classes: V E, EE, V V and EV In this section, we define and study four classes of graphs, based on simple domination properties. These graphs form natural subclasses of balanced graphs. Let v, w be vertices and e, f edges of a graph G. Say that vertex v (edge e) dominates vertex w (edge f ) when NG [v] ⊇ NG [w] (NG [e] ⊇ NG [f ]). Similarly, vertex v (edge e) dominates edge f (vertex w) when NG [v] ⊇ NG [f ] (NG [e] ⊇ NG [w]). A graph G is a V E graph if any odd cycle of G contains a vertex that dominates some edge of the cycle, where the edge is non-incident to the vertex. A graph G is an EV graph if any odd cycle of G contains an edge that dominates some vertex of the cycle. Finally, a graph G is a V V (EE) graph if any odd cycle of it contains a vertex (edge) that dominates some other vertex (edge) of the cycle. On Balanced Graphs 9 4.1 Inclusion relations Let us see the inclusion relations between these graph classes. Theorem 11 Let G be an EV graph. Then G is an EE graph and a V V graph. Proof Let C = {v1 , . . . , v2j+1 } be an odd cycle of G. By hypothesis, as G is an EV graph, there is an edge e = (vi , vi+1 ) of C that dominates a vertex vk of C. Then e = (vi , vi+1 ) dominates e1 = (vk−1 , vk ) and e2 = (vk , vk+1 ), and at least one of these edges is not equal to e. So, G is an EE graph. On the other hand, vi and vi+1 dominate vk , and at least one of them is different from vk . In consequence, G is a V V graph too. ⊔ ⊓ Theorem 12 Let G be an EE graph. Then G is a V E graph. Proof Let C = {v1 , . . . , v2j+1 } be an odd cycle of G. By hypothesis, as G is an EE graph, there is an edge e = (vi , vi+1 ) that dominates an edge f = (vk , vk+1 ) of C (e 6= f ). We may suppose that vi 6= vk+1 , so vi dominates f = (vk , vk+1 ), which implies that G is a V E graph. ⊔ ⊓ Theorem 13 Let G be a V V graph. Then G is a V E graph. Proof Let C = {v1 , . . . , v2j+1 } be an odd cycle of G. By hypothesis, as G is a V V graph, there is a vertex vi that dominates a vertex vk (vi 6= vk ). We may suppose that vk 6= vi−1 , so vi dominates f = (vk , vk+1 ), which implies that G is a V E graph. ⊔ ⊓ Finally, we can determine that these classes of graphs are balanced graphs. Theorem 14 Let G be a V E graph. Then G is a balanced graph. Proof Suppose that AG is not a balanced matrix. So, we have the matrix of Figure 3 as a submatrix A′ in AG , where M1 , . . . , M2k+1 are cliques of G and v1 , . . . , v2k+1 are vertices of G. Then v1 , . . . , v2k+1 is an odd cycle of G and Mi is a clique that contains the edge (vi , vi+1 ) (Mi ∈ M (vi , vi+1 )). But Mi does not contain another vertex vj of the cycle, otherwise there would be a 1 in the position (i, j) of A′ . So Mi ∈ / M (vj ) for j 6= i, i + 1. This fact implies that NG [(vi , vi+1 )] 6⊆ NG [vj ] for j 6= i, i + 1, for any edge (vi , vi+1 ) of the cycle, thus G is not a V E graph. ⊔ ⊓ Corollary 5 V E, EE, V V and EV graphs are perfect graphs. Note: Figure 5 shows examples of minimal graphs belonging to the possible intersections defined by the inclusions among these classes. The examples can be checked with no difficulty. We can see in this figure that the inclusions are proper. Remark 2 Bipartite graphs are EV graphs. Remark 3 V E, EE, V V and EV graphs are hereditary classes of graphs. Flavia Bonomo et al. hs ap r G ct hs ap Gr ed Ba lan c Pe rfe 10 VE VV EE EV Fig. 5 Intersection between all the classes. 4.2 Matrix characterizations Let e1 , . . . , em and v1 , . . . , vn be the edges and vertices of a graph G, respectively. Denote by w1i and w2i the endpoints of the edge ei . We define two matrices in {0, 1}m×n: – AV E (G), whose entry (i, j) is 1 if NG [ei ] ⊆ NG [vj ], and 0 otherwise. – AV V (G), whose entry (i, j) is 1 if NG [w1i ] ⊆ NG [vj ] or NG [w2i ] ⊆ NG [vj ], and 0 otherwise. Clearly, both matrices can be constructed in polynomial time. Theorem 15 A graph G is a V E graph if and only if AV E (G) is a balanced matrix. Proof ⇒) Suppose that AV E (G) is not a balanced matrix. So, we have the following submatrix A′ in AV E (G), where e1 , . . . , e2k+1 are edges of G and v1 , . . . , v2k+1 are vertices of G: On Balanced Graphs 11 e1 e2 e3 . . . e2k+1 v1 1 0 0 . . . 1 v2 1 1 0 . . . 0 v3 0 1 1 . . . 0 . . . v2k+1 ... 0 ... 0 ... 0 . . . . . . ... 1 Fig. 6 Vertex-edge incidence matrix of an odd cycle. Let 1 ≤ i ≤ 2k + 1. Since NG [ei ] ⊆ NG [vi ] ∩ NG [vi+1 ], vi and vi+1 are adjacent, and then v1 , . . . , v2k+1 is an odd cycle of G. Let fi be the edge (vi , vi+1 ). Then NG [ei ] ⊆ NG [fi ]. So, if the vertex vj dominates the edge fi , then it also dominates the edge ei and, therefore, there must be a 1 in the position (i, j) of A′ . So the vertex vj does not dominate the edge fi for j 6= i, i + 1, for any edge fi of the cycle. Thus G is not a V E graph. ⇐) Suppose that G is not a V E graph. Then there is an odd cycle C = {v1 , . . . , v2k+1 } such that, for any ei = (vi , vi+1 ) and any j 6= i, i+1, NG [ei ] 6⊆ NG [vj ]. Now, if we choose the rows of AV E (G) corresponding to e1 , . . . , e2k+1 and the columns of AV E (G) corresponding to v1 , . . . , v2k+1 , we have a vertex-edge incidence matrix of an odd cycle as a submatrix of AV E (G), so it is not a balanced matrix. ⊔ ⊓ Corollary 6 There is a polynomial-time recognition algorithm for V E graphs. Theorem 16 A graph G is a V V graph if and only if AV V (G) is a balanced matrix. Proof ⇒) Suppose that AV V (G) is not a balanced matrix. So, we have the matrix of Figure 6 as a submatrix A′ in AV V (G), where e1 , . . . , e2k+1 are edges of G and v1 , . . . , v2k+1 are vertices of G. Let 1 ≤ i ≤ 2k + 1. By definition of AV V (G), NG [ei ] ⊆ NG [vi ] ∩ NG [vi+1 ], and therefore vi and vi+1 are adjacent. Then v1 , . . . , v2k+1 is an odd cycle of G. Note that, if the vertex vj dominates the vertex vi , there must be a 1 in the position (i, j) of A′ and a 1 in the position (i − 1, j) of A′ (the sums must be understood modulo 2k+1). However, the latter does not occur. So the vertex vj does not dominate the vertex vi for any j 6= i. Thus G is not a V V graph. ⇐) Suppose that G is not a V V graph. Then there is an odd cycle C = {v1 , . . . , v2k+1 } such that, for any i 6= j, NG [vi ] 6⊆ NG [vj ]. If we choose the rows of AV V (G) corresponding to e1 , . . . , e2k+1 and the columns of AV V (G) corresponding to v1 , . . . , v2k+1 , we have a vertex-edge incidence matrix of an odd cycle as a submatrix of AV V (G), so it is not a balanced matrix. ⊔ ⊓ Corollary 7 There is a polynomial-time recognition algorithm for V V graphs. 12 Flavia Bonomo et al. 4.3 A combinatorial algorithm for the maximum stable set in V V graphs The maximum stable set problem can be solved in polynomial time for perfect graphs [19] (and in consequence for balanced graphs and its subclasses too), but the algorithm is based on linear programming. We present here a polynomial time purely combinatorial algorithm (i.e. non LP-based) for the problem of determining the maximum stable set in V V graphs. Lemma 2 Let G be a graph and v, w two vertices of G such that v dominates w. Then there exists a maximum stable set S of G such that v does not belong to S. Proof Let S be a maximum stable set in G. If v does not belong to S, the lemma holds. Otherwise, w cannot belong to S because it is adjacent to v. As v dominates w, S \ {v} ∪ {w} is a maximum stable set that does not contain v. ⊔ ⊓ Theorem 17 There exists a polynomial time combinatorial algorithm to find a maximum stable set for V V graphs. Proof Let G be a V V graph. If there exists a vertex v that dominates another vertex w, then remove v. This procedure is repeated until no more dominating vertices exist. We obtain an induced subgraph G′ that can be constructed in polynomial time. As V V graphs are hereditary, G′ lies in this class. So, G′ has no odd cycle (and in consequence is a bipartite graph). By Lemma 2, a maximum stable set in G′ is a maximum stable set in G. Such a set can be found in O(n5/2 ) time [22]. ⊔ ⊓ 5 Clique graphs of balanced graphs Clique graphs of several classes of graphs have been already characterized. Trees, interval graphs, chordal graphs, block graphs, clique-Helly graphs and Helly circular-arc graphs are some of them [29]. In this section we see that the class of balanced graphs and the class of totally unimodular graphs are fixed classes under the clique operator, i.e. K(BALANCED ) = BALANCED and K(TOTALLY UNIMODULAR) = TOTALLY UNIMODULAR, and finally we present a characterization of clique graphs of V E, EE, V V and EV graphs. First some definitions and lemmas are needed. Let AtG be the transpose matrix of AG . The following lemma is clear. Lemma 3 Let G be a clique-Helly graph. Then AK(G) is the submatrix of AtG obtained by removing the included rows. Define the graph H(G) where V (H(G)) = {q1 , . . . , qk , w1 , . . . , wn }, each qi corresponds to the clique Mi of G, and each wi corresponds to the vertex vi of G. The edges of H(G) are the following: the vertices q1 , . . . , qk induce the graph K(G), the vertices w1 , . . . , wn induce a stable set and wj is adjacent to qi if and only if vj belongs to the clique Mi in G. On Balanced Graphs 13 Theorem 18 [21] Let G be a clique-Helly graph and H(G) as defined above. Then the cliques of H(G) are induced by NG [wi ] for each i, wi is a simplicial vertex of H(G) for every i, and K(H(G)) = G. Let A ∈ Rn×m and B ∈ Rn×k be two matrices. We define the matrix A|B ∈ Rn×(m+k) by (A|B)(i, j) = A(i, j) for i = 1, . . . , n, j = 1, . . . , m and (A|B)(i, m + j) = B(i, j) for i = 1, . . . , n, j = 1, . . . , k. Let In be the n × n identity matrix. Theorem 19 Let G be a clique-Helly graph and |V (G)| = n. Then AH(G) = AtG |In . Proof It follows immediately from the previous theorem. ⊔ ⊓ From Lemma 3 we can deduce the following result, proved in [4] too: Theorem 20 If G is a balanced graph then K(G) is also balanced. Theorem 21 A graph G is balanced if and only if G is clique-Helly and H(G) is balanced. Proof ⇒) If G is a balanced graph, then by Corollary 1, G is a clique-Helly graph. So, we have that AH(G) = AtG |In (Theorem 19), and AG is balanced, so AtG is balanced. On the other hand, all the columns of the vertex-edge incidence matrix of an odd cycle have two nonzero entries, so AH(G) is balanced. ⇐) If G is a clique-Helly graph and H(G) is balanced, G = K(H(G)) (Theorem 18) and then G is balanced (Theorem 20). ⊔ ⊓ The following corollary, mentioned in [25], follows from Theorem 20, Corollary 1 and Theorem 21. Corollary 8 The class of balanced graphs is fixed under K, that is, K(BALANCED ) = BALANCED. Next, we show that similar results hold for the class of totally unimodular graphs. Theorem 22 If G is a totally unimodular graph then K(G) is also totally unimodular. Proof If G is a totally unimodular graph then G is a balanced graph and then G is a clique-Helly graph (Corollary 1). So Lemma 3 holds. If AG is a totally unimodular matrix, then AtG is totally unimodular too, since for every square matrix M , det(M ) = det(M t ). And every submatrix of a totally unimodular matrix is totally unimodular. So, AK(G) is a totally unimodular matrix. ⊔ ⊓ Theorem 23 A graph G is totally unimodular if and only if G is clique-Helly and H(G) is totally unimodular. 14 Flavia Bonomo et al. Proof ⇒) If G is a totally unimodular graph then G is a balanced graph and consequently G is a clique-Helly graph (Corollary 1). We have that AH(G) = AtG |In (Theorem 19), and AG is totally unimodular, so AtG is totally unimodular. Every square submatrix M of AH(G) can be written as M = M1 |M2 , where M1 is a submatrix of AtG and M2 is a submatrix of In . So, using determinant properties, M is singular or det(M ) = ±det(M3 ), where M3 is a square submatrix of M1 . Then, in both cases, det(M ) = 0 or ±1. Therefore H(G) is totally unimodular. ⇐) If G is a clique-Helly graph and H(G) is totally unimodular, G = K(H(G)) (Theorem 18) and then G is totally unimodular (Theorem 22). ⊔ ⊓ Corollary 9 The class of totally unimodular graphs is fixed under K, i.e., K(TOTALLY UNIMODULAR) = TOTALLY UNIMODULAR. Finally, we present a characterization of clique graphs of V E, EE, V V and EV graphs. Let S = {M1 , . . . , M2k+1 } be an odd set of cliques of G, where Mr intersects Mr+1 for r = 1, . . . , 2k + 1 (all the sums must be understood modulo 2k+1). A graph G is a dually EE graph (DEE graph) if for any such a set S there exist i, j, 1 ≤ i, j ≤ 2k + 1, i 6= j, such that Mi ∩ Mi+1 ⊆ Mj ∩ Mj+1 . A graph G is a dually VE graph (DV E graph) if for any such a set S there exist i, j, 1 ≤ i, j ≤ 2k + 1, i 6= j, i + 1 6= j, such that Mi ∩ Mi+1 ⊆ Mj . Theorem 24 Let G be a DEE graph. Then G is a DV E graph. Proof Let S = {M1 , . . . , M2k+1 } a set of cliques of G, where Mi intersects Mi+1 for i = 1, . . . , 2k + 1. By hypothesis, as G is a DEE graph, there are cliques Mi , Mi+1 , Mj , Mj+1 such that Mi ∩ Mi+1 ⊆ Mj ∩ Mj+1 (i 6= j). So Mi ∩ Mi+1 ⊆ Mj , and if i + 1 = j then i 6= j + 1, i + 1 6= j + 1 and Mi ∩ Mi+1 ⊆ Mj+1 , which implies that G is a DV E graph. ⊔ ⊓ Theorem 25 Let G be a DV E graph. Then G is a balanced graph. Proof Suppose that AG is not a balanced matrix. So, we have the matrix of Figure 3 as a submatrix A′ in AG , where M1 , . . . , M2k+1 are cliques of G and v1 , . . . , v2k+1 are vertices of G. Then {M1 , . . . , M2k+1 } is an odd set of cliques of G where Mi intersects Mi+1 for i = 1, . . . , 2k + 1. On the other hand, vi is a vertex that belongs to Mi ∩ Mi+1 but vi does not belong to another clique Mj of the set, otherwise there would be a 1 in the position (j, i) of A′ . So vi ∈ / Mj for j 6= i, i + 1. This fact implies that Mi ∩ Mi+1 6⊆ Mj for j 6= i, i + 1, for any i = 1, . . . , 2k + 1, thus G is not a DV E graph. ⊔ ⊓ Theorem 26 Let G be a graph. – – – – If If If If G G G G is is is is a a a a DV E graph then K(G) is V E. DEE graph then K(G) is EE. V E graph then K(G) is DV E. EE graph then K(G) is DEE. On Balanced Graphs 15 Proof Let G be a graph. Classes DV E, DEE, V E and EE are subclasses of balanced graphs, and balanced graphs are clique-Helly. So, if G belongs to some of these classes, then G is a clique-Helly graph. The vertices of K(G) are the cliques of G, and by Lemma 3 we know that the cliques of K(G) are some M (v) with v ∈ V (G). Let {M1 , . . . , M2k+1 } be an odd cycle in K(G), then Mi intersects Mi+1 in G, for i = 1, . . . , 2k + 1. If G is a DV E graph, there are cliques Mi , Mi+1 , Mj such that Mi ∩ Mi+1 ⊆ Mj (i, i + 1 6= j). Let M (v) be a clique of K(G) that contains Mi and Mi+1 . Then, in G, v lies in Mi ∩ Mi+1 implying that v is in Mj and therefore M (v) contains Mj too. So, in K(G), the vertex Mj dominates the edge (Mi , Mi+1 ) and, as a consequence, K(G) is in V E. If G is a DEE graph, there are cliques Mi , Mi+1 , Mj , Mj+1 such that Mi ∩ Mi+1 ⊆ Mj ∩ Mj+1 (i 6= j). Let M (v) be a clique of K(G) that contains Mi and Mi+1 , then, in G, v lies in Mi ∩ Mi+1 implying that v is in Mj ∩ Mj+1 and therefore M (v) contains Mj and Mj+1 too. So, in K(G), the edge (Mj , Mj+1 ) dominates the edge (Mi , Mi+1 ) and, in consequence, K(G) is in EE. Now, let {M (v1 ), . . . , M (v2k+1 )} be an odd set of cliques in K(G), where M (vi ) intersects M (vi+1 ) for i = 1, . . . , 2k + 1. Then for each i there exists a clique Mi of G such that vi and vi+1 belong to Mi , and then vi and vi+1 are adjacent in G, so v1 , . . . , v2k+1 is an odd cycle in G. If G is in V E, there is a vertex vj of the cycle that dominates the edge (vi , vi+1 ) with j 6= i, i + 1. Let M be a vertex of K(G), M lies in M (vi ) ∩ M (vi+1 ) in K(G), vi and vi+1 belong to M in G, and therefore vj belongs to M too. So M ∈ M (vj ), and in consequence M (vi ) ∩ M (vi+1 ) ⊆ M (vj ). Then K(G) is a DV E graph. If G is in EE, there is an edge (vj , vj+1 ) of the cycle that dominates the edge (vi , vi+1 ) with j 6= i. Let M be a vertex of K(G), M lies in M (vi ) ∩ M (vi+1 ) in K(G), vi and vi+1 belong to M in G, and therefore vj and vj+1 belong to M too. So M ∈ M (vj ) ∩ M (vj+1 ), and in consequence M (vi ) ∩ M (vi+1 ) ⊆ M (vj ) ∩ M (vj+1 ). Then K(G) is a DEE graph. ⊔ ⊓ Theorem 27 Let G be a clique-Helly graph. – – – – G G G G is is is is a a a a DV E graph if and only if H(G) is V E. DEE graph if and only if H(G) is EE. V E graph if and only if H(G) is DV E. EE graph if and only if H(G) is DEE. Proof Let G be a clique-Helly graph and H(G) as defined in Theorem 18, with V (H(G)) = {q1 , . . . , qk , w1 , . . . , wn }, each qi corresponds to the clique Mi of G, and each wi corresponds to the vertex vi of G. By Theorem 18, the cliques of H(G) are NH(G) [wi ] for each i. Then wi and all its incident edges are dominated between themselves, and every vertex in NH(G) (wi ) dominates wi and all its incident edges. Let C be an odd cycle in H(G). If there is a vertex wi in C, then C contains an edge that dominates another edge, and a vertex that dominates an edge non incident to it. 16 Flavia Bonomo et al. EE H DEE Fig. 7 Intersection between the dual classes EE and DEE. If there is not such a vertex, C is an odd cycle {qr1 , . . . , qr2s+1 } that corresponds to an odd set of cliques {Mr1 , . . . , Mr2s+1 } of G, such that Mri intersects Mri+1 for i = 1, . . . , 2s + 1. If G is a DV E graph, there are cliques Mri , Mri+1 , Mrj such that Mri ∩ Mri+1 ⊆ Mrj (i, i + 1 6= j). Let NH(G) [wl ] be a clique of H(G) that contains qri and qri+1 . Then, in G, vl lies in Mri ∩ Mri+1 implying that vl is in Mrj and therefore, in H(G), NH(G) [wl ] contains qrj too. So, in H(G), the vertex qrj dominates the edge (qri , qri+1 ) and, in consequence, H(G) is V E. If G is a DEE graph, there are cliques Mri , Mri+1 , Mrj , Mrj+1 such that Mri ∩ Mri+1 ⊆ Mrj ∩ Mrj+1 (i 6= j). Let NH(G) [wl ] be a clique of H(G) that contains Mri and Mri+1 . Then, in G, vl belongs to Mri ∩ Mri+1 implying that vl belongs to Mrj ∩ Mrj+1 . Therefore, in H(G), NH(G) [wl ] contains qrj and qrj+1 too. So, in H(G), the edge (qrj , qrj+1 ) dominates the edge (qri , qri+1 ) and, in consequence, H(G) is EE. Now, let {NH(G) [wr1 ], . . . , NH(G) [wr2s+1 ]} be an odd set of cliques in H(G), where NH(G) [wri ] intersects NH(G) [wri+1 ] for i = 1, . . . , 2s + 1. Then for each i there exists a vertex q ∈ NH(G) [wri ] ∩ NH(G) [wri+1 ]. So vri and vri+1 belong to the corresponding clique M of G, and then vri and vri+1 are adjacent in G, so vr1 , . . . , vr2s+1 is an odd cycle in G. If G is a V E graph, there is a vertex vrj of the cycle that dominates the edge (vri , vri+1 ) with j 6= i, i + 1. Let ql be a vertex of H(G), ql lies in NH(G) [wri ]∩NH(G) [wri+1 ] in H(G), vi and vi+1 belong to Ml in G, and therefore vj belongs to Ml too. So ql belongs to NH(G) [wrj ], and in consequence NH(G) [wri ] ∩ NH(G) [wri+1 ] ⊆ NH(G) [wrj ]. Then H(G) is DV E. If G is a EE graph, there is an edge (vrj , vrj+1 ) of the cycle that dominates the edge (vri , vri+1 ) with j 6= i. Let ql be a vertex of H(G), ql lies in NH(G) [wri ] ∩ NH(G) [wri+1 ] in H(G), vri and vri+1 belong to Ml in G, and therefore vrj and vrj+1 belong to Ml too. So ql belongs to NH(G) [wrj ] ∩ NH(G) [wrj+1 ] in H(G), and in consequence NH(G) [wri ] ∩ NH(G) [wri+1 ] ⊆ NH(G) [wrj ] ∩ NH(G) [wrj+1 ]. Then H(G) is DEE. The converse properties follow from Theorem 18 and Theorem 26 applied to H(G). ⊔ ⊓ On Balanced Graphs 17 VE K DVE Fig. 8 Intersection between the dual classes V E and DV E. Corollary 10 K(DEE) = EE and K(EE) = DEE. Corollary 11 K(DV E) = V E and K(V E) = DV E. The following result by Escalante is needed to analyse clique graphs of V V graphs. Theorem 28 [15] If G is a clique-Helly graph then K 2 (G) is the subgraph of G obtained by removing the dominated vertices. Theorem 29 Let G be a graph. If G is a V V graph then K 2 (G) is a bipartite graph. Proof If G is a V V graph then G is clique-Helly (Corollary 1). Every odd cycle of G has a dominated vertex, and therefore, by Theorem 28, K 2 (G) is a bipartite graph. ⊔ ⊓ Theorem 30 Let G be a graph. Then K(G) is a bipartite graph if and only if G is a clique-Helly graph and H(G) is an EV graph. Proof ⇒) Let G be a graph, V (G) = {v1 , . . . , vn } and M (G) = {M1 , . . . , Mk }. Since K(G) is a bipartite graph, G is clique-Helly because any set of pairwise intersecting cliques has at most two elements. Clearly, V (H(G)) = V (K(G)) ∪ {w1 , . . . , wn } as in the definition of H(G). Also, K(G) is a bipartite graph and by the definition of H(G), every odd cycle C of H(G) must contain a vertex wi from {w1 , . . . , wn }. By Theorem 18, wi is a simplicial vertex, so the edges of C incident to wi dominate the vertex wi , and then H(G) is an EV graph. ⇐) If G is a clique-Helly graph and H(G) is an EV graph, it is a V V graph too. So by Theorem 29, K 2 (H(G)) = K(G) is a bipartite graph. ⊔ ⊓ Corollary 12 K 2 (V V ) = K 2 (EV ) = the class of bipartite graphs. Proof We will prove that K 2 (EV ) ⊆ K 2 (V V ) ⊆ BIPARTITE ⊆ K 2 (EV ) and therefore the three classes are the same. The first inclusion holds because EV ⊆ V V . The second inclusion follows from Theorem 29. Now, for every 18 Flavia Bonomo et al. bipartite graph G we have that K(H(G)) = G and by Theorem 30 applied to H(G), H 2 (G) is an EV graph and K 2 (H 2 (G)) = G. So the third inclusion holds too. ⊔ ⊓ The class K −1 (BIPARTITE ) has been analysed and characterized by forbidden subgraphs in [27]. Corollary 13 K(V V ) = K(EV ) = K −1 (BIPARTITE ). Proof Let G be a V V graph. By the last corollary, K 2 (G) = K(K(G)) is bipartite so K(G) belongs to K −1 (BIPARTITE ). Therefore K(EV ) ⊆ K(V V ) ⊆ K −1 (BIPARTITE ). On the other hand, let G be a graph belonging to K −1 (BIPARTITE ), then by Theorem 30 H(G) is EV and G = K(H(G)). So K −1 (BIPARTITE ) ⊆ K(EV ) ⊆ K(V V ) ⊆ K −1 (BIPARTITE ) and we have that the three sets are equal. ⊔ ⊓ As a consequence of this result, we deduce the existence of pure combinatorial algorithms to find a maximum clique-independent set and a minimum clique-transversal for V V graphs. Corollary 14 There exists a polynomial time combinatorial algorithm to find a maximum clique-independent set and a minimum clique-transversal for V V graphs. Proof Let G be a V V graph. Then K(G) belongs to K −1 (BIPARTITE ) and can be constructed in polynomial time. Moreover, a maximum cliqueindependent set of G can be obtained from a maximum stable set of K(G), and a minimum clique-transversal of G can be constructed from a minimum clique covering of K(G). Since the graphs K −1 (BIPARTITE ) are K1,3 -free [27] there exists a polynomial time combinatorial algorithm for maximum stable set in these graphs [28]. As K(G) is also perfect, we can use the polynomial time combinatorial algorithm for minimum clique covering in K1,3 -free perfect graphs [23]. So, the result holds. ⊔ ⊓ Finally, we can see that K −1 (BIPARTITE ) graphs are a subclass of DEE. Theorem 31 K −1 (BIPARTITE ) ⊆ DEE. Proof Let G ∈ K −1 (BIPARTITE ). Suppose that there exists an odd set S = {M1 , . . . , M2k+1 } of cliques of G, where Mi intersects Mi+1 for i = 1, . . . , 2k and M2k+1 intersects M1 . Then the corresponding vertices in K(G) form an odd cycle, but K(G) is a bipartite graph, so such a set does not exist, and G is DEE. ⊔ ⊓ Note 1 In Figure 9, we can see that all these inclusions are proper. Acknowledgements We would like to thank the referees for the careful reading and for all the suggestions and corrections, which certainly contributed to improve the paper. First and third author are partially supported by UBACyT Grants X184 and X212, PICT ANPCyT Grant 11-09112 and PID Conicet Grant 644/98, Argentina and “International Scientific Cooperation Program CONICyT/SETCIP”, 19 d hs ap Gr E DV D Bal an ce On Balanced Graphs EE artite) K -(1 bip Fig. 9 Inclusion between the classes. Chile-Argentina. Second author is partially supported by FONDECyT Grant 1030498 and Millennium Science Nucleus “Complex Engineering Systems”, Chile and “International Scientific Cooperation Program CONICyT/SETCIP”, ChileArgentina. Fourth author is partially supported by Conselho Nacional de Desenvolvimento Cientı́fico e Tecnológico, CNPq, and Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro, FAPERJ, Brasil. References 1. Anstee, R., Farber, M.: Characterizations of totally balanced matrices. J. Algorithms 5, 215–230 (1984) 2. Berge, C.: Les problemes de colorations en théorie des graphes. Publ. Inst. Stat. Univ. Paris 9, 123–160 (1960) 3. Berge, C.: Sur certains hypergraphes généralisant les graphes biparties. In: P. Erdös, A. Rényi, V. Sós (eds.) Combinatorial Theory and Applications, pp. 119–133. North–Holland, Amsterdam (1970) 4. Berge, C.: Balanced matrices. Math. Program. 2, 19–31 (1972) 5. Berge, C.: Notes sur les bonnes colorations d’un hypergraphe. Cah. Cent. Etud. Rech. Oper. 15, 219–223 (1973) 6. Berge, C., Las Vergnas, M.: Sur un théorème du type König pour hypergraphes. Ann. N.Y. Acad. Sci. 175, 32–40 (1970) 7. Cameron, K., Edmonds, J.: Existentially polytime theorems. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 1, 83–100 (1990) 8. Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory, Ser. B 18, 138–154 (1975) 9. Conforti, M.: Personal communication (2004) 10. Conforti, M., Cornuéjols, G., Rao, R.: Decomposition of balanced matrices. J. Comb. Theory, Ser. B 77, 292–406 (1999) 11. Conforti, M., Cornuéjols, G., Vušković, K.: Balanced matrices. Discrete Math. To appear. 12. Cornuéjols, G.: Combinatorial Optimization: Packing and Covering. SIAM, Philadelphia (2001) 13. Dahlhaus, E., Manuel, P., Miller, M.: Maximum h-colourable subgraph problem in balanced graphs. Inf. Process. Lett. 65, 301–303 (1998) 20 Flavia Bonomo et al. 14. Duchet, P.: Hypergraphs. In: R. Graham, M. Grötschel, L. Lovász (eds.) Handbook of Combinatorics, pp. 381–432. Elsevier, Amsterdam (1995) 15. Escalante, F.: Über iterierte clique-graphen. Abh. Math. Semin. Univ. Hamb. 39, 59–68 (1973) 16. Farber, M.: Characterizations of strongly chordal graphs. Discrete Math. 43, 173–189 (1983) 17. Fulkerson, D., Hoffman, A., Oppenheim, R.: On balanced matrices. Math. Program. 1, 120–132 (1974) 18. Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs, Ann. Discrete Math., vol. 57, second edn. North–Holland, Amsterdam (2004) 19. Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981) 20. Guruswami, V., Pandu Rangan, C.: Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Appl. Math. 100, 183–202 (2000) 21. Hamelink, R.: A partial characterization of clique graphs. J. Comb. Theory, Ser. B 5, 192–197 (1968) 22. Hopcroft, J., Karp, R.: An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225–231 (1973) 23. Hsu, W., Nemhauser, G.: Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs. Discrete Math. 37, 181–191 (1981) 24. Lehel, J., Tuza, Z.: Neighborhood perfect graphs. Discrete Math. 61, 93–101 (1986) 25. Lubiw, A.: Orderings and some combinatorial optimization problems with geometric applications. Ph.D. thesis, Department of Computer Science, University of Toronto, Toronto (1985) 26. Prisner, E.: Hereditary clique-Helly graphs. J. Comb. Math. Comb. Comput. 14, 216–220 (1993) 27. Protti, F., Szwarcfiter, J.: Clique-inverse graphs of bipartite graphs. J. Comb. Math. Comb. Comput. 40, 193–203 (2002) 28. Sbihi, N.: Algorithmes de recherche d’un stable de cardinalite maximum dans un graphe sans etoile. Discrete Math. 29, 53–76 (1980) 29. Szwarcfiter, J.: A survey on Clique Graphs. In: C. Linhares Sales, B. Reed (eds.) Recent Advances in Algorithms and Combinatorics, pp. 109–136. Springer– Verlag, New York (2003) 30. Tsukiyama, S., Idle, M., Ariyoshi, H., Shirakawa, Y.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505–517 (1977)