Subdivisions, Parity and Well-Covered Graphs Yair Caro SCHOOL OF EDUCATION DEPARTMENT OF MATHEMATICS UNIVERSITY OF HAIFA—ORANIM TIVON 36006—ISRAEL E-mail: zeac603@uvm.haifa.ac.il Received March 12, 1996 Abstract: A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm) characterization of the class called 3-separable graphs. Also we consider parity graphs studied by Finbow and Hartnell and answer the question posed by them (Ars. Combin. 40 (1995)) by proving, among other results, that the decision problem: ''given a graph G which is a parity graph, is G also well-covered graph?'' is in the class CO-NPC. In addition we supply some complexity results that answer some problems due to Plummer (Quaestiones Math. 16 (1993)) and c 1997 John Wiley & Sons, Inc. J Finbow, Hartnell, and Whitehead (Discrete Math. 125 (1994)). Graph Theory 25: 85–94, 1997 Keywords: well-covered, complexity, parity graphs 1. INTRODUCTION (A MINI-SURVEY) Plummer called a graph well-covered if every independent set is contained in a maximum independent set [20]. An alternative definition, more suitable for complexity treatment and an algorithmic approach, is that a graph G is well-covered if the size of a maximum independent set (the independence number-denoted α(G)) is equal to the size of the smallest maximal independent set (the independent domination number—denoted here α1 (G)), namely if α(G) = α1 (G). An interesting algorithmic property of well-covered graphs is that the greedy algorithm for producing a maximal independent set always produces a maximum independent set when applied to well-covered graphs. Combinatorial structures sharing this greedy property were recently c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/010085-10 86 JOURNAL OF GRAPH THEORY discussed by Caro, Sebo and Tarsi [4] and Caro, Ellingham and Ramey [5]. Research on wellcovered graphs can be grouped into four main directions, which we briefly summarize below. 1. STRUCTURAL CHARACTERIZATIONS Given a family F of graphs, to supply a list of all the members of F which are well-covered, or at least to describe their structure. The following families have been discussed and a complete characterization is known. 1.1) 1.2) 1.3) 1.4) 1.5) 1.6) 1.7) 1.8) 1.9) 1.10) 1.11) Graphs with girth, g(G) ≥ 5 [10], Graphs without cycles of length 4 and 5 [11]. K(1, 3)-free 4-regular 4-connected graphs [29]. K(1, 3)-free 4-connected planar graphs [29]. Bipartite graphs [7, 23, 28]. Connected graphs with α(G) = |G|/2 [7, 28, 21] (|G| = |V (G)|, the order of G). 3-regular graphs [2, 22]. k-trees, Cn -trees, block graphs, unicyclic graphs [21]. Chordal graphs, circular arc graphs [27]. Total graphs [30]. Generalized Petersen graphs [30] When a structural characterization seems elusive the second strategy is to devise algorithms for efficiently computing α(G) and α1 (G) and testing for equality, α(G) = α1 (G), in polynomial time. 2. COMPUTING α(G) = α (G) IN POLYNOMIAL TIME 2.1) Graphs with bounded tree width (including series-parallel graphs, and hence outer-planar graphs [7]. 2.2) Chordal graphs (interval graphs, split graphs) [7, 27]. 2.3) Permutation graphs [7]. When this strategy fails one tries to devise an algorithm that tests directly the well-coveredness property. 3. POLYNOMIAL TIME ALGORITHMS TO DECIDE WELL-COVEREDNESS 3.1) 3.2) 3.3) 3.4) K1,3 -free graphs [26] (extending [19]). Perfect graphs with bounded clique-size [7] (including in particular bipartite graphs). Decomposition graphs [3]. Graphs with maximum degree ∆(G) ≤ c(log |G|)1/3 [5]. 4. INTRACTABLE FAMILIES OF GRAPHS 4.1) Deciding if a given graph is well-covered is CO-NPC [6, 25]. 4.2) For n ≥ 4 deciding if a K1,n -free graph is well-covered is CO-NPC [4]. SUBDIVISIONS, PARITY, AND WELL-COVERED GRAPHS 87 With 4.1 and 4.2 in mind a natural candidate for investigation is the class of 2-degenerate graphs. A graph G is called 2-degenerate if for any induced subgraph H of G, the minimum degree of H is at most two, δ(H) ≤ 2. The class of 2-degenerate graphs has been extensively studied with respect to various graph parameters. Surprisingly the complexity status of the independence number in the class of 2-degenerate graphs seems to have been overlooked. Exploring the role of subdivisions and their effect on α(G) we show that computing α(G) in the class of 2-degenerate graphs is NP-hard even when restricted to 2-degenerate planar graphs of maximum degree 3. Thus it is clear that computing when α1 (G) = α(G) is not a suitable strategy even for the simplest subclasses of the class of the 2-degenerate graphs. A complete characterization is given for 3-separable graphs which are well-covered. A graph is called 3-separable if any two vertices of degree at least three are independent. The class of parity graphs, i.e., those in which the cardinality of every maximal independent set has the same parity is considered in [8, 9]. This notion is extended in [5] to graphs whose vertices are labelled by elements of a finite abelian group A, and a graph G with a given labeling is called Awell-covered if maximal independent sets have the same sum of labels in A. Finbow and Hartnell gave a characterization of parity graphs with girth at least six while Caro, Ellingham and Ramey [5] gave a polynomial time algorithm to decide A-well-coveredness provided ∆(G) ≤ c(log |G|)1/3 . We shall supply a general solution to a problem raised by Finbow and Hartnell [9], by proving: Let G be a graph which is both Zm -well-covered and K1,3m+1 -free, then it is a CO-NPC problem to decide whether G is well-covered. The case Z2 (= parity graph) answers the question by Finbow and Hartnell. In addition, several complexity results are treated which are related to questions posed by Plummer [21], and Whitehead [12]. 5. SUBDIVISIONS AND 3-SEPARABLE GRAPHS An elementary 1-subdivision is the result of replacing an edge (u, v) by a path of length two (u, w, v) where deg w = 2. An elementary 2-subdivision is the result of replacing an edge (u, v) by a path of length three (u, w, z, v) where deg w = deg z = 2. Notice that neither 1-subdivision nor 2-subdivision preserve well-coveredness since C4 and C5 are both well-covered graphs but a 2-subdivision of C4 as well as a 1-subdivision of C5 produce C6 which is not well-covered. Lemma 1. α(G) + 1. Suppose H is obtained from G by an elementary 2-subdivision. Then α(H) = Proof. Suppose x, y ∈ V (G) and (x, y) ∈ E(G) and let H be the graph obtained by a 2-subdivision of (x, y) by replacing this edge with the path (x, a, b, y). Assume first, that W ⊆ V (G) is a maximum independent set in G, |W | = α(G). Then at most one of the vertices x, y can belong to W , say y 6∈ W . Then T = W ∪ {b} is independent in H and hence α(H) ≥ |T | = |W | + 1 = α(G) + 1. To prove the converse inequality, α(H) ≤ α(G)+1, let T ⊆ V (H) be a maximum independent set in H, α(H) = |T |. 88 JOURNAL OF GRAPH THEORY Case 1. If {x, y} ⊆ T then {a, b} ∩ T = ∅ and W = T − {x} is independent in G, thus α(H) = |W | + 1 ≤ α(G) + 1. Case 2. If {x, y} ∩ T = ∅ then at most one of the vertices a, b belong to T . If, say, b 6∈ T , then W = T − {a} is independent in G and α(H) ≤ |W | + 1 ≤ α(G) + 1. Otherwise, precisely one of the vertices x, y belong to T , say y ∈ T : Case 3. If x 6∈ T, y ∈ T then b 6∈ T and W = T − {a} is independent in G, so that α(H) = |T | ≤ |W | + 1 ≤ α(G) + 1. This completes the proof. We need a few more definitions. For a class F of graphs and a polynomial f denote by D(1, f, F ), respectively D(2, f, F ), the class of graphs obtained from F by applying on a member G ∈ F at most f (|G|) elementary 1-subdivisions, respectively 2-subdivisions, and denote by D(2, F ) the class of graphs obtained by applying on a member G ∈ F any number of elementary 2-subdivisions. Theorem 1. Let F be a family of graphs and f be a polynomial. 1) The complexity of computing α(G) for G ∈ F is the same as the complexity of computing α(H) for H ∈ D(2, f, F ). 2) If for G in F computing α(G) is polynomial, then so is for H in D(2, F ) the computation of α(H). 3) There exists a class F of bipartite graphs and a polynomial f such that computing α(G) for G in F is polynomial, but for H in D(1, f, F ) computing α(H) is NP-hard. 4) Let m > 0 be fixed and Fm be the class of graphs in which V3 = {u ∈ V : deg u ≥ 3} satisfies |V3 | ≤ m log2 |V |. Then computing α(G), for G ∈ Fm , can be done in polynomial time. Proof. 1) Suppose H is obtained from G ∈ F by applying t elementary 2-subdivisions, t ≤ f (|G|). Then, by Lemma 1, |H| = |G| + 2t and α(H) = α(G) + t. Hence, if computing α(G) is polynomial, so is computing α(H) and if computing α(G) is NP-hard, then so is computing α(H). 2) Follows using the same reasoning as in (1) since α(H) = α(G) + t. 3) Consider the following construction (for which I am indebted to Noga Alon). Let G(V, E) be any graph on n vertices. Let H be the bipartite graph on the classes of vertices V1 and V2 where V1 = {v1 : v ∈ V }, V2 = {u2 : u ∈ V } and v1 u2 is an edge in H whenever vu is an edge in E. Also v1 u2 is an edge, called a ‘‘special edge’’ , in H for every vertex v1 = v = u = u2 . Let H 0 be the graph obtained from H by applying 1-subdivision for each of the special edges v1 u2 in H. Let V3 = V (H 0 ) \ V (H). Clearly computing α(H) can be done in polynomial time since H is bipartite (see, e.g., [13]), and also |H 0 | = |H|+n (hence f (n) = n). We claim that α(H 0 ) = α(G) + n, and this will prove the NP-hardness (because G is arbitrary). Indeed if I is an independent set in G, then {u1 : u ∈ I} ∪ {u2 : u ∈ I} ∪ {u3 : u ∈ V \ I} is an independent set in H 0 , showing that α(H 0 ) ≥ 2α(G) + (n − α(G)) = α(G) + n. On the other hand, if W is a maximum independent set on n + t vertices in H 0 , then since |W ∩ {v1 , v2 , v3 }| ≤ 2 for all v ∈ V it follows that |W ∩ {v1 , v2 , v3 }| = 2 for at least t distinct vertices v ∈ V (for otherwise |W | ≤ n − (t − 1) + 2(t − 1) = n + t − 1 < n + t, SUBDIVISIONS, PARITY, AND WELL-COVERED GRAPHS 89 a contradiction). Define A = {u : |W ∩ {u1 , u2 , u3 }| = 2}. Then |A| ≥ t, and A must be an independent set in G. Thus α(G) ≥ t and α(H 0 ) ≤ α(G) + n, completing the proof of the claim. 4) To compute α(G) it is sufficient to find, for every independent set φ ⊆ A ⊆ V3 , the independence number of hV \ {V3 ∪ N (A)}i, namely α(G) = max{|A| + αhV \ {V3 ∪ N [A]}i : φ ⊆ A ⊆ V3 , A is an independent set}. But hV \ {V3 ∪ N [A]}i is a union of cycles and paths and computing the independence number for such graphs is linear, i.e., O(n). Hence α(G) can be calculated in time O(2|V3 | · |V3 |2 · n) = O(nm+1 (log2 n)2 m2 ). An immediate consequence of Theorem 1 is: Theorem 2. Computing α(G) in the class of 3-separable planar graphs with maximum degree 3 is NP-hard. Proof. It is well known [13] that computing α(G) in the class of planar cubic graphs is NPhard. Let G be a planar cubic graph on n vertices and apply an elementary 2-subdivision on every edge of G, to produce a graph H which is a 3-separable planar graphs with ∆(H) = 3. Now |H| = n + 2|E(G)| and α(H) = α(G) + |E(G)| and, by Theorem 1, computing α(H) is NP-hard. It follows from Theorem 2 that testing if α(G) = α1 (G) is no strategy for 2-degenerate graphs and in particular for 3-separable graphs. However, using the theorem of Finbow, Hartnell and Nowakowski [10], a complete characterization of the class of 3-separable well-covered graphs is now presented. Theorem 3. Let G be a connected 3-separable well-covered graph. Then G ∈ {K1 , K2 , C3 , C4 , C5 , C7 } ∪ S2,m ∪ S3,m ∪ S5,m ∪ S5,m,n , where 90 JOURNAL OF GRAPH THEORY Proof. It is easy to verify that all the graphs listed in Theorem 3 are indeed connected 3separable well-covered graphs. The bulk of the proof is to show that this list is complete. We consider three cases with respect to the presence of C3 , C4 and girth g(G) ≥ 5. Case 1. There exists a triangle C3 . If G = C3 then we are done, hence assume G 6= C3 is connected. Clearly by 3-separabiltiy if V (C3 ) = {u, v, w} then w.l.o.g. deg u = deg w = 2 and deg v ≥ 3. Suppose first all vertices of G are at distance at most 1 from v. Then clearly A = {v} and B = any maximal independent set in V (G) \ {v} are both maximal and |B| > |A|. Hence G is not well-covered. Hence suppose there are vertices at distance at least 2 from v. Let A = {x ∈ V (G) : d(x, v) = 2} and let B = {y ∈ V : d(y, v) = 1, y 6= {u, w} and y has no neighbor at distance 2 from v}. If B 6= φ then deg y ≤ 2 for each y ∈ B since (y, v) ∈ E(G). Construct a maximal independent set S1 as follows: Choose a maximal independent set S0 in G \ {v ∪ N (v)} and take S1 = S0 ∪ {v}. Construct another maximal independent set S2 as follows: Choose S0 as above and add to it the vertex w, and a maximal independent set of hBi. Since B 6= φ, |S2 | > |S1 | and G is not well-covered. Hence it remains to consider B = φ. Write D = N (A) ∩ N (v) and observe that for y ∈ D deg y = 2. Suppose again S is a maximal independent set in hG \ {v ∪ N (v)}i. If for some x ∈ A, x 6∈ S, then there must be some y ∈ D uncovered by S and both S1 = S ∪ {y, u} and S2 = S ∪ {v} are maximal with |S1 | > |S2 | and G is not well-covered. Hence |A| = |D| and both hAi and hDi are independent sets. But now it follows for any x ∈ A that deg x = 1. For otherwise if for some x ∈ A deg x ≥ 2, then let z be a neighbor of x not in D and construct a maximal independent set of hG\{v ∪N (v)}i starting from z to obtain a forbidden maximal set as was shown above (since it misses x ∈ A). Hence it follows that G ∈ S3,m for some m ≥ 1. Case 2. There exists a C4 . Observe first that by Case 1 if there exists a C4 then G must be triangle-free, since none of the well-covered graphs in Case 1 contains a C4 . If G = C4 we are done. Hence suppose G 6= C4 is connected. Let V (C4 ) = {x, y, u, v} and suppose (x, y), (u, v) 6∈ E(G). Also w.l.o.g. deg x = deg y = 2, deg u ≥ 2 and deg v ≥ 3. Suppose first deg u = 2. Construct a maximal independent set S0 of hG \ V (C4 )i containing a neighbor of v. Then both S1 = S0 ∪ {u} and S2 = S0 ∪ {x, y} are maximal but |S2 | > |S1 | and G is not well-covered. Hence assume deg u, deg v ≥ 3. Suppose there exists a vertex w ∈ N (v) \ N (u). Construct a maximal independent set S1 containing w and u. Clearly (S1 \ {u}) ∪ {x, y} is a larger independent set. Hence G is not well-covered. So it remains to consider only the graphs in which every w ∈ V \ {u, v} is adjacent to both u and v (which are of degree ≥ 3) and hence S1 = {u, v}, S2 = V \ {u, v} are both maximal with |S2 | > |S1 | and G is not well-covered. Case 3. Girth (G) ≥ 5. Call a C5 basic if it does not contain two adjacent vertices of degree at least 3 in G. The Finbow-Hartnell-Nowakowski Theorem [10] states that if girth (G) ≥ 5 then G is a connected well-covered graph iff either G belongs to a list of six exceptional graphs or V (G) is the union of vertex disjoint basic C5 's and pendant edges that form a matching, whereby a pendant edge we mean both a pendant vertex (of degree = 1) and its neighbor. Now in the list of exceptional graphs only K1 and C7 are 3-separable. Otherwise G must be of girth = 5 since girth ≥ 6 implies that G is not 3-separable by the girth 5 theorem, as every vertex on any cycle must be of degree ≥ 3. SUBDIVISIONS, PARITY, AND WELL-COVERED GRAPHS 91 Also if there are two basic C5 's in G, then on the trail connecting them all the vertices must be of degree ≥ 3 by the girth 5 theorem (including of course the end-points of the trail that belong to the C5 's), and this violates the 3-separability. Hence G contains precisely one basic C5 and either one or two vertices on it are of degree ≥ 3. Again with the pendant edges part of the girth 5 theorem, it follows easily that G ∈ S5,m or G ∈ S5,m,n . Lastly it remains to consider acyclic graph, namely trees. But using either Ravindra's theorem [23] or the girth 5 theorem [10] it is easily shown that the only 3-separable well-covered trees are precisely K1 , K2 and those in S2,m . 6. COMPLEXITY RESULTS Given two graphs G and H define G×H as the graph obtained by replacing each vertex v ∈ V (G) by a copy H(v) of v and by further joining all vertices of a copy H(u) to all vertices of a copy H(v) if and only if v is adjacent to u in G. Theorem 4. The decision problem ‘‘is G well-covered’’ remains CO-NPC even if it is given that G is both K1,3m+1 -free and Zm -well-covered for any fixed positive integer m ≥ 1. Proof. For m = 1 this is a theorem proved in [4] (where it is understood that a Z1 -wellcovered graph is just a well-covered graph). Suppose m ≥ 2, then showing the problem is in CO-NP is clear, since one should present two maximal independent sets of distinct cardinalities. Showing completeness is by reduction from the case m = 1 namely recognizing well-covered K1,4 -free graphs is a CO-NPC problem [4]. So let G be an instance for the problem of recognizing K1,4 -free well-covered graphs. Let H = K̄m , i.e., the empty graph on m vertices. Consider F = G × H = G × K̄m as an instance for our problem. Clearly this is a polynomial (linear) reduction, and also by the definition of G × H it follows that: (1) For every maximal independent set in F , if it contains at least one vertex from a copy K̄m (v), then it contains all of K̄m (v). (2) Every maximal independent set in F has cardinality 0(mod m). Hence F is a Zm -wellcovered graph. Also for every vertex u ∈ V (F ), deg u ≡ 0(mod m). (3) B ⊂ V (G) is a maximal independent set in G if and only if ∪v∈B V (K̄m (v)) is a maximal independent set in F . (4) F is K1,3m+1 -free since each vertex u ∈ V (F ) is adjacent to exactly m disjoint sets N1 , . . . , Nm and, for each 1 ≤ i ≤ m, u ∪ Ni induces a copy of the original closed neighborhood of u in G which contains no four independent vertices. Hence F is K1,3m+1 free. (5) Hence by (1)–(4) we infer that F is well-covered iff G is well-covered and that F is a Zm -well-covered K1,3m+1 -free graph, proving the CO-NPC. Finbow, Hartnell, and Whitehead [12] considered the following: Definition. Let M (t) be the class of graphs having maximal independent sets of at most t distinct sizes. Clearly M (1) is the class of well-covered graphs. They gave a characterization for girth 8 M (2) graphs. Here we prove: Theorem 5. Recognizing membership in M (t) is CO-NPC even in the class of K1,4 -free graphs. 92 JOURNAL OF GRAPH THEORY Proof. By presenting t + 1 maximal independent sets of distinct sizes we infer that M (t) is a CO-NP problem. Let G be an instance for the M (1) problem. Consider H = tG, namely, t disjoint copies of G. This is a linear reduction and H is K1,4 -free. Observe that H ∈ M (t) if and only if G ∈ M (1). This follows since a maximal independent set A in H consists of the union of t + 1 maximal independent sets Ai of the ith copy Gi of G. Hence, if G ∈ M (1), then all the cardinalities |Ai | above are the same and, in fact, H ∈ M (1) ⊂ M (t). If G 6∈ M (1), then there exist two maximal independent sets B, D of G such that |B| = b > d = |D|. But then we will choose the following t + 1 maximal independent sets in H of distinct sizes. For 0 ≤ i ≤ t take Si = (∪ij=0 Bj ) ∪ (∪tj=i+1 Dj ), where Bj , Dj are copies of B and D in the jth copy of G. Clearly each Si is a maximal independent set in H. Furthermore |Si | = ib+(t−i)d and as b > d it follows that |S0 | < |S1 | < · · · < |St |, proving the theorem. In his survey paper [21] Plummer discusses the graph classes Wn : A graph G belongs to Wn if, given any collection of n disjoint independent sets {I1 , . . . , In } in G, there exist disjoint maximum independent sets J1 , . . . , Jn such that Ij ⊆ Jj for each j = 1 · · · n. Here we show: Theorem 6. For any positive integer n, recognizing a member in Wn is CO-NPC even for K1,4 -free graphs. Proof. Clearly G 6∈ Wn can be verified by presenting a collection of n disjoint maximal independent sets, at least one of which is not maximum, so the problem is a CO-NP problem. Let G be a K1,4 -free instance for the well-covered graph problem (M (1) and W1 above). Consider the graph H = G × Kn (with the operation × as used in Theorem 4). This is a linear reduction. Observe the following facts concerning G and H. (1) H is K1,4 -free since vertices in G are replaced by Kn in H, and members of the same copy of Kn have the same neighbors not in Kn . (2) Any collection of n disjoint independent sets in H, {I1 , . . . , In } can be completed to a collection of disjoint maximal independent sets {J1 , . . . , Jn } such that Ij ⊆ Jj , j = 1 · · · n. This is because each Ij contains at most one vertex of each copy Kn (v) (for every vertex v ∈ V (G)), and hence we can label the vertices of H such that Kn (v) = {v1 , . . . , vn } and, if Ij ∩ Kn (u) 6= φ, then uj ∈ Ij . But now we can complete each Ij to a maximal independent set by completing the corresponding (unindexed copy of Ij ) set in G to a maximal independent set. (3) By the former section if G is well-covered then H ∈ Wn as all its maximal independent sets are maximum. Hence any collection {I1 , . . . , In } of disjoint independent sets can be extended to the required {J1 , . . . , Jn }. On the other hand if G is not well-covered then there exists maximal independent sets A, B ⊆ V (G) such that |A| > |B|. But then in H = G × Kn , and using (2), we can take I1 = A, I2 = B, Ij = φ, j = 3, . . . , n and clearly {I1 , I2 , . . . , In } cannot be completed to a collection of disjoint maximum independent sets {J1 , . . . , Jn } such that Ij ⊂ Jj , j = 1, . . . , n. Hence H 6∈ Wn , proving the theorem. Remark. Having Theorem 4 it is clear that versions of Theorem 5 and Theorem 6 can be proved to show that membership in Wn or in M (t) remains a CO-NPC problem even if we are given that G is a Zm -well-covered graph. SUBDIVISIONS, PARITY, AND WELL-COVERED GRAPHS 93 7. ACKNOWLEDGMENT I am indebted to the two referees for inspiring and helpful suggestions. References [1] S. R. Campbell, Some results on cubic well-covered graphs, Ph.D. thesis, Vanderbilt University (1987). [2] S. R. Campbell, M. N. Ellingham, and Gordon F. Royle, A characterisation of well-covered cubic graphs, J. Combin. Math. Combin. Comput. 13 (1993), 193–212. [3] Y. Caro, J. Rojas, and S. Ruiz, A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs, Czech. Math. J, 46 (1996), 413–419. [4] Y. Caro, A. Sebö, and M. Tarsi, Recognizing greedy structures, J. Algorithms 20 (1996), 137–156. [5] Y. Caro, M. Ellingham, and J. Ramey, Local structure when all maximal independent sets have equal weight, submitted. [6] V. Chvátal and P. J. Slater, A note on well-covered graphs, Quo Vadis, Graph Theory?, Ann. Discrete Math. 55, North-Holland, Amsterdam (1993), 179–182. [7] N. Dean and J. Zito, Well covered graphs and extendability, Discrete Math. 126 (1994), 67–80. [8] A. Finbow and B. L. Hartnell, A game related to covering by stars, Ars Combin. 16-A (1983), 189–198. [9] A. Finbow and B. Hartnell, A characterization of parity graphs containing no cycle of order five or less, Ars Combin. 40 (1995), 227–234. [10] A. Finbow, B. Hartnell, and R. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser. B 57 (1993), 44–68. [11] A. Finbow, B. Hartnell, and R. Nowakowski, A characterization of well-covered graphs that contain neither 4- nor 5-cycles, J. Graph Theory 18 (1994), 713–721. [12] A. Finbow, B. Hartnell, and C. Whitehead, A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets, Discrete Math. 125 (1994), 153–167. [13] M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NPcompleteness, W. H. Freeman, San Francisco (1979). [14] S. L. Gasquoine, B. Hartnell, R. Nowakowski, and C. Whitehead, Techniques for constructing wellcovered graphs with no 4-cycles, J. Combin. Math. Combin. Comput. 17 (1995), 65–87. [15] G. Gunther, B. Hartnell, and C. A. Whitehead, On 2-packings of graphs of girth at least 9, Congr. Numer. 110 (1995), 211–222. [16] B. L. Hartnell, On maximal radius 2 independent sets, Congr. Numer. 48 (1985), 179–182. [17] B. L. Hartnell, On the local structure of well-covered graphs without 4-cycles, Ars Combin., to appear. [18] B. Hartnell and C. A. Whitehead, On k-packings of graphs, preprint (1995). [19] M. Lesk, M. D. Plummer, and W. R. Pulleyblank, Equimatchable graphs, Graph theory and combinatorics (B. Bollobás, Ed.), Academic Press, London (1984), 239–254. [20] M. D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970), 91–98. [21] M. D. Plummer, Well-covered graphs: a survey, Quaestiones Math. 16 (1993), 253–287. [22] J. E. Ramey, Well-covered graphs with maximum degree three and minimal non-well-covered graphs, Ph.D. thesis, Vanderbilt University (1994). [23] G. Ravindra, Well-covered graphs, J. Combin. Inform. System Sci. 2 (1977), 20–21. [24] S. Ruiz, Randomly decomposable graphs, Discrete Math. 57 (1985), 123–128. 94 JOURNAL OF GRAPH THEORY [25] R. S. Sankaranarayana and L. K. Stewart, Complexity results for well-covered graphs, Networks 22 (1992), 247–262. [26] D. Tankus and M. Tarsi, Well-covered claw-free graphs, J. Combin. Theory Ser. B 66 (1996), 293–302. [27] E. Prisner, J. Topp, and P. D. Vestergaard: Well-covered simplicial, chordal and circular arc graphs, J. Graph Theory 21 (1996), 113–119. [28] O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982), 177–187. [29] B. Hartnell and M. D. Plummer, On 4-connected claw-free well-covered graphs, Discrete Appl. Math. 64 (1996), 57–66. [30] J. Topp and P. Vestergaard, Some classes of well-covered graphs, manuscript R-93-2009/1993, Aalborg University.

1/--страниц