Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 237–245
A parallel algorithm for computing the critical
independence number and related sets
Ermelinda DeLaViña ∗
Department of Computer and Mathematical Sciences
University of Houston—Downtown, Houston, TX 77002
Craig E. Larson †
Department of Mathematics and Applied Mathematics
Virginia Commonwealth University, Richmond, VA 23284
Received 9 July 2010, accepted 10 May 2012, published online 28 October 2012
Abstract
An independent set Ic is a critical independent set if |Ic| − |N(Ic)| ≥ |J | − |N(J)|,
for any independent set J . The critical independence number of a graph is the cardi-
nality of a maximum critical independent set. This number is a lower bound for the in-
dependence number and can be computed in polynomial-time. The existing algorithm
runs in O(n2.5
√
m/ log n) time for a graph G with n = |V (G)| vertices and m edges.
It is demonstrated here that there is a parallel algorithm using n processors that runs in
O(n1.5
√
m/ log n) time. The new algorithm returns the union of all maximum critical
independent sets. The graph induced on this set is a König-Egerváry graph whose compo-
nents are either isolated vertices or which have perfect matchings.
Keywords: Critical independent set, critical independence number, independence number, matching
number, König-Egerváry graph.
Math. Subj. Class.: 05C69
1 Introduction
A new faster parallel algorithm is given for finding maximum critical independent sets and
calculating the critical independence number of an arbitrary graph.
∗Work supported in part by the United States Department of Defense and resources of the Extreme Scale
Systems at Oak Ridge National Laboratories.
†Corresponding author.
E-mail addresses: delavinae@uhd.edu (Ermelinda DeLaViña), clarson@vcu.edu (Craig E. Larson)
Copyright c© 2013 DMFA Slovenije
238 Ars Math. Contemp. 6 (2013) 237–245
The following notation is used throughout: the vertex set of a graph G is V (G), the
order of G is n = n(G) = |V (G)|, the set of neighbors of a vertex v is NG(v) (or simply
N(v) if there is no possibility of ambiguity), the set of neighbors of a set S ⊆ V (G) in G
is NG(S) = ∪u∈SN(u) (or simply N(S) if there is no possibility of ambiguity), the set
N [S] = N(S)∪S, and the graph induced on S isG[S]. All graphs are assumed to be finite
and simple.
A set I ⊆ V (G) of vertices is an independent set if no pair of vertices in the set are
adjacent. The independence number α = α(G) is cardinality of a maximum independent
set (MIS) of vertices in G. An independent set of vertices Ic is a critical independent set if
|Ic|−|N(Ic)| ≥ |J |−|N(J)|, for any independent set J . A maximum critical independent
set (MCIS) is a critical independent set of maximum cardinality. The critical independence
number of a graph G, denoted α′ = α′(G), is the cardinality of a maximum critical inde-
pendent set. If Ic is a maximum critical independent set, and so α′(G) = |Ic|, then clearly
α′ ≤ α. The critical difference d is max{|Ic| − |N(Ic)| : Ic is an independent set}.
Critical independent sets are of interest for both practical and theoretical reasons. By a
theorem of Butenko and Trukhanov, any critical independent set can be extended to a max-
imum independent set [4]. Zhang and Ageev gave polynomial-time algorithms for finding
critical independent sets [17, 1]. Thus, finding a critical independent set is a polynomial-
time technique for reducing the search for the well-known widely-studied NP-hard problem
of finding a maximum independent set in a graph [7]. Maximum critical independent sets
are central in the investigation of the structure of maximum independent sets, a connection
via the Independence Decomposition Theorem, recounted in the next section.
The existing algorithm for finding a MCIS and calculating α′ runs inO(n2.5
√
m/log n)
time [11]. It is demonstrated here that there is a parallel algorithm using n processors that
runs in O(n1.5
√
m/ log n) time. The new algorithm finds the set H of vertices which
are in some maximum critical independent set, that is, the union of all MCISs. The graph
induced on this set is a König-Egerváry graph whose non-trivial components each have a
perfect matching.
2 The set H of vertices in some MCIS
The correctness of the algorithm presented in the next section depends on the following
decomposition theorem, a corollary of, and equivalent to, the Independence Decomposition
Theorem in [12]. A matching in a graph is a set of pairwise non-incident (or independent)
edges. The matching number µ of a graph is the cardinality of a maximum matching. A
König-Egerváry graph is one where α+ µ = n.
Theorem 2.1. (Larson, [12]) For any graph G, there is a unique set X ⊆ V (G) such that
1. α(G) = α(G[X]) + α(G[Xc]),
2. G[X] is a König-Egerváry graph,
3. for every non-empty independent set I in G[Xc], |N(I)| > |I|, and
4. for every maximum critical independent set Jc of G, X = Jc ∪N(Jc).
According to the theorem there is a unique set X ⊆ V (G) such that, for any maximum
critical independent set Ic, Ic ∪ N(Ic) = X . For any graph G let X = X(G) be the set
guaranteed by Theorem 2.1. Call G[X] the distinguished König-Egerváry subgraph of G.
König-Egerváry graphs were first characterized by Deming [6] and Sterboul [16] in the
E. DeLaViña and C. E. Larson: A parallel algorithm for computing the critical. . . 239
1970s. The first author’s Graffiti.pc program conjectured (number 329 in [5]) a characteri-
zation in terms of the critical independence number: a graph G is a König-Egerváry graph
if, and only if, α(G) = α′(G). The conjecture was first proven by Larson in [12]. In [14]
Levit & Mandrescu extended the statement of this result as follows.
Theorem 2.2. (Levit & Mandrescu, [14]) The following are equivalent:
1. G is a König-Egerváry graph,
2. there is a maximum independent set of G that is a MCIS,
3. every maximum independent set of G is a MCIS,
Figure 1: The vertices Ic = {a, b} form a (maximum cardinality) critical independent set;
this set of vertices can be extended to a maximum independent set of the graph. According
to Theorem 2.1 the setsX = Ic∪N(Ic) = {a, b, c, d} andXc = V \X = {e, f, g} induce
a decomposition of the graph into a König-Egerváry subgraphG[X] and one,G[Xc], where
every non-empty independent set of vertices I has more than |I| neighbors.
It will now be shown that the graph induced on the set H (the union of all MCISs) is
König-Egerváry. This fact will be used in the proof of correctness of the parallel algorithm.
While the class of König-Egerváry graphs contains all the bipartite graphs (by the König-
Egerváry Theorem, [15]) and subgraphs of bipartite graphs are bipartite, it is not true in
general that subgraphs of König-Egerváry graphs are König-Egerváry. So it is worth noting
that G[X] is König-Egerváry, G[H] is a subgraph of G[X], and G[H] is König-Egerváry.
The following results are required in the proof of Theorem 2.5.
Lemma 2.3. (The Matching Lemma, [11]) If I is a critical independent set, then there is a
matching from N(I) to I .
Let Ω = Ω(G) be the set of maximum independent sets in G. The core of a graph G,
denoted core(G), is defined to be ∩{S : S ∈ Ω}, namely, the set of vertices which are in
every maximum independent set; and ξ = ξ(G) = |core(G)|. This notation follows [3].
Theorem 2.4. (Levit & Mandrescu, [13]) If G is a König-Egerváry graph, then G has a
perfect matching if, and only if, | ∩ {S : S ∈ Ω(G)}| = | ∩ {V (G)− S : S ∈ Ω}|.
Theorem 2.5. If Ic is a maximum critical independent set of a graph G, X = Ic ∪N(Ic),
and H is the union of all maximum critical independent sets, then
1. H ∪N(H) = X ,
2. G[H] is a König-Egerváry graph,
240 Ars Math. Contemp. 6 (2013) 237–245
3. I is a maximum independent set of G[H] if, and only if, I is a MCIS of G and
α′(G) = α(G[H]),
4. The non-trivial components of G[H] have a perfect matching,
5. If I0 are the isolated vertices in G[H] then α(G[H]) = |I0|+ 12 |H \ I0|.
Proof. Let Ic be a MCIS of a graph G and X = Ic ∪ N(Ic). By Theorem 2.1 it follows
that, for any MCIS Jc of G, Jc ∪ N(Jc) = X . Let Ωc be the set of MCISs of G. Then
H ∪N(H) = ∪{Jc : Jc ∈ Ωc}∪N(∪{Jc : Jc ∈ Ωc}) = [∪{Jc : Jc ∈ Ωc}]∪ [∪{N(Jc) :
Jc ∈ Ωc}] = ∪{Jc ∪N(Jc) : Jc ∈ Ωc} = X , proving 1.
Now, Ic ⊆ H . Let H ′ = H \ Ic. So n(G[H]) = |Ic|+ |H ′|. Furthermore, α(G[H]) ≥
|Ic|. By construction H ′ ⊆ N(Ic). By the Matching Lemma there is a matching from
N(Ic) into Ic inG. Thus there is a matching fromH ′ into Ic inG[H] and µ(G[H]) ≥ |H ′|.
So α(G[H]) + µ(G[H]) ≥ |Ic|+ |H ′| = n(H) and, for any graph, α + µ ≤ n, it follows
that α(G[H]) + µ(G[H]) = n(G[H]), that is, G[H] is König-Egerváry, proving 2. It now
follows easily that α(G[H]) = |Ic| and thus that Ic is a maximum independent set ofG[H],
proving one direction of 3.
Now let I be a maximum independent set of G[H]. So I is an independent set in G[X],
|I| ≥ |Ic|, and α(G[X]) ≥ |I|. It will now be argued that α(G[X]) = |Ic| and, hence,
|Ic| = |I|. Theorem 2.1 implies that G[X] is König-Egerváry. Then it is not difficult to see
that the Matching Lemma implies that µ(G[X]) = |N(Ic)|. Finally, we have n(G[X]) =
α(G[X]) + µ(G[X]) ≥ |Ic|+ |N(Ic)| = |X| = n(G[X]). The claim them follows. Then,
since I and Ic are maximum independent sets of G[H], I ∪ N(I) ⊆ H ∪ N(H) = X .
N(I) ⊆ X\I andN(Ic) ⊆ X\Ic. It is worth noting here that,N(I) is the set of neighbors
of I in graph G (as opposed to graph G[H]). No use is made in this proof of neighbors of
a set of vertices in graph G[H] and no subscripts are ever required for clarity. To continue,
it follows that |N(I)| ≤ |X \ I| and |N(Ic)| = |X \ Ic|. Since |X \ I| = |X \ Ic|,
it follows that |N(I)| ≤ |N(Ic)| and, thus, that |I| − |N(I)| ≥ |I| − |N(Ic)|. But,
if |I| − |N(I)| > |Ic| − |N(Ic)|, Ic is not a critical independent set, contradicting our
assumption. Thus |I| − |N(I)| = |Ic| − |N(Ic)|, and I is a critical independent set of G,
proving the other direction of 3.
Let I0 be the set of isolated vertices in G[H]. These are contained in any maximum
independent set of G[H]. Let I ′c = Ic \ I0 and H ′ = H \ I0. It is then claimed that
G[H ′] has a perfect matching. Let v ∈ H ′. Suppose v ∈ core(G[H ′]), that is, v is in every
maximum independent set ofG[H ′]. Then v is in every maximum independent set ofG[H]
and, thus, in every maximum critical independent set of G. But H is the set of vertices in
some maximum critical independent set of G. So no vertex in N(v) is in any maximum
independent set of G[H], or in any maximum critical independent set of G, which is a
contradiction. Thus | ∩ {S : S ∈ Ω(G[H ′])}| = 0. By similar reasoning it can be shown
that | ∩ {V (G[H ′]) − S : S ∈ Ω(G[H ′])}| = 0. Thus | ∩ {S : S ∈ Ω(G[H ′])}| =
| ∩ {V (G[H ′])− S : S ∈ Ω(G[H ′])}|. Theorem 2.4 then implies that G[H ′] has a perfect
matching, proving 4.
It is clear that, sinceG[H] is König-Egerváry, andG[H ′] has a perfect matching,G[H ′]
is also König-Egerváry; that is, α(G[H ′]) + µ(G[H ′]) = n(G[H ′]). Since n(G[H ′]) =
2µ(G[H ′]), it follows that α(G[H ′]) = 12n(G[H
′]) = 12 |H \ I0|. Finally α(G[H]) =
|I0|+ α(G[H ′]) = |I0|+ 12 |H \ I0|, proving 5.
E. DeLaViña and C. E. Larson: A parallel algorithm for computing the critical. . . 241
3 A parallel MCIS algorithm
The criterion given for testing whether a vertex belongs to a critical independent set begins
by passing to a certain bipartite graph. The computational speed of the following algorithm
is due to the fact that the independence number of a bipartite graph can be computed in
polynomial time.
Definition 3.1. For a graphG, the bi-double graphB(G) has vertex set V ∪V ′, where V ′ is
a copy of V . If V = {v1, v2, . . . , vn}, let V ′ = {v′1, v′2, . . . , v′n}. Then, (x, y′) ∈ E(B(G))
if, and only if, (x, y) ∈ E(G).
The bi-double graph B(G) of G can also be described as K2G, the cartesian product
of K2 and G.
Corollary 3.2. (Larson, [11]) A graph G contains a non-empty critical independent set
if, and only if, there is a vertex v ∈ V (G) such that α(B(G)) = α(B(G) − {v, v′} −
N({v, v′}) + 2.
In fact, the proof of this corollary actually shows that a vertex v satisfying the specified
condition is in some critical set. It is also shown in [11] that any critical independent set
can be extended to a MCIS. These results are now combined in a form directly useful in
the current context.
Theorem 3.3. (MCIS Criterion) A vertex v in a graph G is in some MCIS if, and only if,
α(B(G)) = α(B(G)− {v, v′} −N({v, v′}) + 2.
The following algorithm results in the set of all vertices which are in some maximum
critical independent set. Step 4 requires n iterations—but, due to the MCIS Criterion, these
n tests can be run independently on n processors. This is where the parallelization takes
place.
MCIS subgraph algorithm
1. Construct B(G).
2. a := α(B(G)).
3. H := ∅.
4. For each vertex v in V (G),
(a) t := α(B(G)− {v, v′} −N({v, v′}) + 2.
(b) If t = a, H := H ∪ {v}.
According to Theorem 3.3 these steps will result in the construction of a set H consist-
ing of all vertices which are in some MCIS. This can be extended in various ways to find
the following invariants or sets.
1. Find α′. In order to calculate α′, the remaining step is to identify the trivial and non-
trivial components ofH . Let I0 be the isolated vertices inH . Then, by Theorem 2.5,
α′(G) = |I0|+ 12 (|H \ I0|).
242 Ars Math. Contemp. 6 (2013) 237–245
2. Find X . In order to calculate the decomposition guaranteed by the Independence
Decomposition Theorem, it remains to find the neighbors of the vertices inH . Again
by Theorem 2.5, H ∪N(H) = X . Let Xc = V (G) \X . Then G[Xc] will have the
property that, for every non-empty independent set J , |N(J)| > |J |.
3. Find a MCIS Ic of G. In order to find a MCIS, Theorem 2.5 implies that it suffices
to find a maximum independent set Ic in H . Then Ic is a MCIS in G.
Since B(G) is a bipartite graph on 2n vertices, calculating a maximum matching of
B(G) and, hence, calculating α(B(G)) requires O(n1.5
√
m/ log n) operations, using the
algorithm of Alt, et al. [2]. This algorithm will be run once and then a second time inde-
pendently on each of n processors. So the total running time is still O(n1.5
√
m/ log n).
If M is a matching in a graph G and w is a vertex incident to an edge in M , let w′ be
the vertex matched to w under M . The new algorithm can now be stated. The parallelism
occurs in step 1.
The parallel MCIS algorithm
1. Find H .
2. Find the set I0 of isolated vertices in G[H]. H0 := I0.
3. If H \H0 = ∅, I := I0. STOP.
4. Find a maximum matching M of G[H].
5. Let w ∈ H \H0.
6. N1 := N(I0 ∪ {w}), M1 := {v′ : v ∈ N1}, I1 := I0 ∪ M1, H1 := I1 ∪ N1
(=H0 ∪N1 ∪M1).
7. i := 1.
8. While H \Hi 6= ∅:
(a) i. If Hi 6= Hi−1: Ni+1 := N(Ii).
ii. Else if Hi = Hi−1:
A. Let w ∈ H \Hi.
B. Ni+1 := N(Ii ∪ {w}),
(b) Mi+1 := {v′ : v ∈ Ni+1}, Ii+1 := Ii ∪ Mi+1. Hi+1 := Ii+1 ∪ Ni+1,
i := i+ 1.
9. I := Ii.
Theorem 3.4. If G is a graph then the set I produced by the Parallel MCIS algorithm is a
maximum critical independent set of G.
Proof. LetG be a graph,H be the set of vertices in some maximum critical independent set
ofG, andM be the maximum matching ofG[H] produced by the Parallel MCIS algorithm.
Theorem 2.5 implies that α′(G) = α(G[H]). Thus it is enough to show that the set I
produced by this algorithm is a maximum independent set of G[H].
Let I0 be the set of isolated vertices in G[H] and H ′ = H \ I0. It was shown that G[H]
is a König-Egerváry graph whose non-trivial components have perfect matchings. G[H ′]
is the union of the non-trivial components. So M is a perfect matching of G[H ′].
E. DeLaViña and C. E. Larson: A parallel algorithm for computing the critical. . . 243
The algorithm will first be described for the convenience of the reader. The first step
is to identify the isolated vertices. These can be extended to a maximum independent set
of G[H]. Then choose any vertex w among the remaining vertices. By the definition of
the set H , there is a MCIS and, by Theorem 2.5, this is a maximum independent set of
G[H]. So there is maximum independent set I of G[H] which contains w. The neighbors
of this vertex cannot be in I but each of these vertices is incident to some edge in the perfect
matching M of G[H] and, since one vertex from every edge of M must be in I , it follows
that the vertices matched to N(w) under M must be in I . In general, having constructed
an independent set J , the neighbors of J cannot be in the maximum independent set but,
since one vertex from every edge in M must be in the maximum independent set, the
vertices matched to N(J) under M must be in the set. If at some point there are no new
vertices in N(J), but the vertices in the graph have not been used up, an arbitrary vertex
can be selected from the remaining vertices, added to the independent set, and the process
continued.
The set I0 is an independent set, H0 = I0, and there is a maximum independent set of
G[H] containing I0. Assume that after the (k − 1)th iteration of the while loop, Ik is an
independent set and there is a maximum independent set of G[H] containing Ik. It will be
shown that Ik+1 is an independent set and there is a maximum independent set of G[H]
which contains Ik+1.
If H \ Hk = ∅ after the (k − 1)th iteration of the while loop, then H = Hk and I is
a maximum independent set of G[H]. Assume then that H \ Hk 6= ∅ after the (k − 1)th
iteration of the while loop. Hk is formed by (possibly) adding vertices to Hk−1, namely,
N(Ik−1) \Hk−1 together with the vertices matched to these under M . Either Hk 6= Hk−1
or Hk = Hk−1. Note that, in either case, by construction, Nk ⊆ Nk+1, Mk ⊆ Mk+1,
Ik ⊆ Ik+1, and Hk ⊆ Hk+1.
In the first case, Hk \Hk−1 6= ∅. Hk is formed by adding the vertices Nk \Nk−1 and
their neighbors Mk \Mk−1 = Ik \ Ik−1 under the matching M . The vertices Mk \Mk−1
may or may not have neighbors outside ofHk. Nk+1 = N(Ik),Mk+1 = {v′ : v ∈ Nk+1},
Ik+1 = Ik ∪Mk+1, and Hi+1 = Ii+1 ∪Ni+1. By assumption Ik is an independent set and
there is a maximum independent set of G[H] containing Ik. The vertices in Ik+1 are the
vertices in Ik together with the vertices matched to the neighbors of Ik under M . Let I be
a maximum independent set of G[H] containing Ik. It cannot contain any neighbor of Ik.
Since any maximum independent set I of G[H] must contain one vertex from each edge of
M , I must contain the vertices matched to N(Ik) under M . Thus Ik+1 is an independent
set and it can be extended to a maximum independent set of G[H].
In the case where Hk = Hk−1, the kth step in the while loop of the algorithm (step
8) works as follows: A vertex w is selected from from H \ Hk. Since Ik is independent
and w /∈ N(w), Ik+1 = Ik ∪ {w} is an independent set. By assumption there is a MCIS
containingw and, following Theorem 2.5, there is a maximum independent set I containing
w. Each edge inM must be incident to some vertex in I . Let I ′ = (I \Hk)∪Ik. It remains
to be shown that I ′ is a maximum independent set of G[H]. Since Hk = Ik ∪ N(Ik) it
follows that I ′ is an independent set. It is now enough to show that, for every edge xy in
M , either x or y is in I ′. Either x or y is in I . Assume x ∈ I . If x /∈ I ′ then x ∈ Hk. But
then by the construction of Hk, y is matched to x under M and y is also in Hk. But Ik is a
maximum independent set in G[Hk]. So either x or y must be in Ik and, thus I ′. So Ik+1
is contained in a maximum independent set.
244 Ars Math. Contemp. 6 (2013) 237–245
The MCIS Subgraph algorithm, which produces H , requires O(n1.5
√
m/ log n) oper-
ations. Finding a maximum matching of G[H] requires the same order or of operations.
The remaining steps only require finding the neighbors of sets of vertices. So the total
running time of Parallel MCIS Algorithm is O(n1.5
√
m/ log n).
4 Acknowledgment and future research
We would like to thank an anonymous referee who pointed us to state-of-the-art references
on maximum matching algorithms (including [8, 9, 10]). The referee notes that algorithm
performance depends on edge density: some algorithms perform better for sparse graphs
while others perform better for dense graphs.
The referee also suggests that future investigation of the time complexity of the algo-
rithm presented above would be of interest in the case that there are n2 or n3 processors.
The presented algorithm requires use of n processors; the problem naturally breaks into n
cases following Theorem 3.3. We do not know of a way to break the problem down further.
References
[1] A. Ageev, On finding critical independent and vertex sets, SIAM J. Discrete Mathematics 7
(1994), 293–295.
[2] H. Alt, N. Blum, K. Melhorn and M. Paul, Computing a maximum cardinality matching in a
bipartite graph in time O(n1.5
√
m/ logn), Information Processing Letters 37 (1991), 237–
240.
[3] E. Boros, M. Golumbic and V. Levit, On the Number of Vertices belonging to all Maximum
Stable Sets of a Graph, Discrete Applied Mathematics 124 (2002), 17–25.
[4] S. Butenko and S. Trukhanov, Using Critical Sets to Solve the Maximum Independent Set
Problem, Operations Research Letters 35 (2007), 519–524.
[5] E. DeLaViña, Written on the Wall II, Conjectures of Graffiti.pc, http://cms.uhd.edu/
faculty/delavinae/research/wowII/index.htm.
[6] R. W. Deming, Independence Numbers of Graphs—an Extension of the Koenig-Egervary The-
orem, Discrete Mathematics 27 (1979), 23–33.
[7] M. Garey and D. Johnson, Computers and Intractability, W. H. Freeman and Company, New
York, 1979.
[8] N. J. A. Harvey, Matchings, Matroids and Submodular Functions, Massachusetts Institute of
Technology Ph.D. thesis, 2008.
[9] A. Jindal, G. Kochar and M. Pal, Maximum Matchings via Glauber Dynamics, Arxiv preprint
arXiv:1107.2482, 2011.
[10] K. Kaya, J. Langguth, F. Manne and B. Uc, Experiments on Push-Relabel-based Maximum
Cardinality Matching Algorithms for Bipartite Graphs, Technical Report TR/PA/11/33, CER-
FACS, Toulouse, France, 2011.
[11] C. E. Larson, A Note on Critical Independence Reductions, Bulletin of the Institute of Combi-
natorics and its Applications 51 (2007), 34–46.
[12] C. E. Larson, Critical Independent Sets and an Independence Decomposition Theorem, Euro-
pean Journal of Combinatorics 32 (2011), 294–300.
[13] V. E. Levit and E. Mandrescu, On α+-stable König-Egerváry graphs, Discrete Mathematics
263 (2003) 179–190.
E. DeLaViña and C. E. Larson: A parallel algorithm for computing the critical. . . 245
[14] V. E. Levit and E. Mandrescu, Critical Independent Sets and König-Egerváry Graphs, Graphs
and Combinatorics 28 (2012), 243–250.
[15] L. Lovasz, M. D. Plummer, Matching Theory, North Holland, Amsterdam, 1986.
[16] F. Sterboul, A characterization of the graphs in which the transversal number equals the match-
ing number, Journal of Combinatorial Theory. Series B 27 (1979), 228–229.
[17] C.-Q. Zhang, Finding critical independent sets and critical vertex subsets are polynomial prob-
lems, SIAM J. Discrete Mathematics 3 (1990), 431–438.