close

Вход

Забыли?

вход по аккаунту

?

Dominating sets with small clique covering number

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
4
Размер файла
121 Кб
Теги
clique, small, number, covering, sets, dominating
1/--страниц
Пожаловаться на содержимое документа