Extending matchings in graphs-a survey

Discrete Mathematics 127 (1994) 2777292 North-Holland 277 Extending matchings in graphs : A survey Michael D. Plummer* Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA Received 27 November 1990 Revised 14 September 1991 Abstract Gallai and Edmonds independently obtained a canonical decomposition of graphs in terms of their maximum matchings. Unfortunately, one of the degenerate cases for their theory occurs when the graph in question has a perfect matching (also known as a l-factor). Kotzig, Lovasz and others subsequently developed a further decomposition of such graphs. Among the ‘atoms’ of this de- composition is the family of hicritical graphs. (A graph G is bicritical if G-u-c has a perfect matching for every choice of two points u, u in C.) So far such graphs have resisted further decomposition procedures. Motivated by these mysterious graphs, we introduced the following definition. Let p and n be positive integers with n <(p - 2)/2. Graph G is n-exrendable if G has a matching of size n and every such matching extends to (i.e. is a subset of) a perfect matching in G. It is clear that if a graph is bicritical, it is I-extendable. A more interesting result is that if a graph is 2-extendable, it is either bipartite or bicriticai. It is also true that if a graph is n-extendable, it is also (n - I)-extendable. Hence, for nonbipartite graphs we have a nested sequence of families of &critical graphs to study. In this paper, we survey a variety of results obtained over the past few years concerning n-extendable graphs. In particular, we describe how the property of n-extendability interacts with such other graph parameters as genus, toughness, claw-freedom and degree sums and generalized neighborhood conditions. We will also investigate the behavior of matching extendability under the operation of Cartesian product. The study of n-extendability for planar graphs has been, and continues to be, of particular interest. 1. Introduction, terminology and some motivation For any terminology not defined in this paper, the reader is directed to either [23] or [3]. Let G be any connected graph. A set of lines M L E(G) is called a matching if they are independent, i.e. no two of them share a common endpoint. A matching is said to be perfect if it covers all points of G. (Hereafter in this paper, ‘perfect matching’ Correspondence to: Michael D. Plummer, Department of Mathematics, Vanderbilt University, Box 1543 Station B, Nashville, TN 37240, USA. *Work supported by ONR Contract # NOO014-85-K-0488. 0012-365X/94/$07.00 0 1994-Elsevier Science B.V. All rights reserved SSDI 0012-365X(92)00485-C 278 M.D. Plummer will often be abbreviated as ‘pm’.) Let Q(G) denote the number of perfect matchings in graph G. There are other areas of science (see [23]) in which it is of interest to determine Q(G). However, it seems very unlikely that an efficient algorithm for computing @(G) will ever be found. In particular, Valiant [48] proved the following result concerning the complexity of this task. Theorem 1.1. The problem of determining Q(G) is #P-complete - and hence NP-hard - even when G is bipartite. So, as is so often the case in mathematics, when a function cannot be computed exactly, we turn instead to a search for bounds. In particular, the material to follow in this paper can be said to be motivated by the search for a nontrivial lower bound for the parameter Q(G). It was noted first by Lo&z [20] that a class of graphs called bicritical play an important role in bounding the number of perfect matchings. (A graph G is said to be bicritical if G-U-V has a perfect matching for every choice of a pair of points, u and v.) Theorem 1.2. If G is k-connected and contains a perfect matching, but is not bicritical, then Q(G) 2 k!. In the author’s opinion, the role of the property of bicriticality in the above theorem is somewhat counterintuitive, and therefore intriguing. After all, it is trivial to see that a bicritical graph has the property that each of its lines lies in a perfect matching. So why should not bicritical graphs have an ‘enormous’ number of perfect matchings, when in a sense, the opposite is true? It is no surprise, then, to note that bicritical graphs have played (and continue to play) an important role in studies involving a lower bound for Q(G). In the past 20 years or so, considerable effort has been devoted to developing a canonical decomposition theory for graphs with perfect matchings. We shall now present the barest of outlines of this effort and refer the interested reader to [23] - and to the list of references to be found therein - for a much more detailed treatment. Let G be a graph containing a perfect matching and suppose n is a positive integer such that n< 1 V(G)1/2. Graph G will be called n-extendable if every set of n indepen- dent lines extends to (i.e. is a subset of) a pm. We begin our discussion of the decomposition theory by assuming that each line of the graph G under consideration lies in at least one pm for G. (In other word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 s, assume that G is 1-extendable. Such graphs are also sometimes called matching-covered. See [21].) Clearly, lines lying in no pm can be ignored when attempting to count the total number of pm’s in the graph. Moreover, the determination of all such ‘forbidden’ lines can be carried out in polynomial time by applying the Edmonds matching algorithm at most [E(G)1 times. E.xiending matchings in graphs: A suroey 219 We now encode each perfect matching in G as a binary vector of length IE(G)I, where thejth entry is a 1 if line j of G belongs to the pm and is a 0, if it does not. Take the linear span of all such binary vectors over the reals, ‘R The dimension of this space is called the real rank ofG and is denoted by r%(G). Clearly, r%(G)< D(G) and hence we have a lower bound of the type sought. However, can the quantity r%(G) is efficiently computed? The answer to this question is ‘yes’, fortunately, but we need to lay a bit more groundwork first. We call a bicritical graph which, in addition, is 3-connected, a brick. It is a fact - although a highly non-trivial one - that a decomposition theory exists for graphs with perfect matchings which terminates in a list of bricks associated with the parent graph. Moreover, this list of bricks is an invariant of the graph and the list can be determined in polynomial time. (See [22].) Denote the number of such bricks of G by b(G). We then can exactly compute r%(G) via the following beautiful result due to Edmonds ca Theorem 1.3. If G is any 1-extendable graph, then The careful reader may have noted by now that it follows immediately from the definition of a bicritical graph that no bipartite graph can be bicritical, let alone a brick. On the other hand, it is easy to find 1-extendable bipartite graphs. Such graphs will yield no bricks in the decomposition procedure, but it is worthwhile to note that the equation of Theorem 1.3 still holds, although in this case, B(G)=O. This result, for the special case of bipartite graphs, actually predates the general formula of Theorem 1.3 and is due to Naddef [26]. Corollary 1.4. If G is any 1-extendable bipartite graph, then r,(G)=IE(G)(-IV(G)I+2. In the most recent version of the decomposition procedure referred to above (and called the tight cut decomposition procedure by Lovasz [22]), in addition to the invariant list of bricks obtained, there is a second list of building blocks called braces. Although these graphs do not figure in the rank formula stated above, as do the bricks, they are deserving of mention in a paper on matching extension. In particular, a bipartite graph is a brace if it is 2-extendable. At this point, we stop to ask the question: are there any well-known classes of graphs for which @(G) can always be exactly determined in polynomial time? The best known such class is the class of planar graphs. This was proved long before the development of the decomposition theory discussed above by Kasteleyn [14, 151 who also gave an algorithm for counting the pms of a planar graph. Although this procedure was presented before complexity of algorithms attracted much attention, 280 M.D. Plummer fortunately Kasteleyn’s algorithm is easily seen to be polynomial. Kasteleyn showed that if one could direct the lines of an undirected graph G so as to obtain a Pfufian orientation of G, then @P(G) was just the value of the determinant of a certain matrix associated with the oriented graph, and hence obtainable in polynomial time. He then showed that one could always find such an orientation when graph G was planar. (For the definition of a Pfaffian orientation, as well as a more detailed discussion of the so-called ‘Kasteleyn method, see [23, Chap. 81.) In a much more recent result, Vazirani and Yannakakis [49] have demonstrated the following important relationship between the bricks and braces of a graph and Pfaffian orientations. Theorem 1.5. An arbitrary graph G has a Pfajian orientation if and only if all of its bricks and braces have such an orientation. There are several interesting and closely related complexity questions about Pfaf- fian orientations of graphs which remain unresolved. (1) Does a given graph have a Pfaffian orientation? (2) Is a given orientation of a graph a Pfaffian orientation? Recently, Vazirani and Yannakakis [49] have demonstrated that (1) and (2) are polynomially equivalent. In fact, in the case of bipartite graphs, questions (1) and (2) are polynomially equivalent to yet a third unsettled question: (3) Given a directed graph, does it contain a directed cycle of even length? The tight set decomposition procedure yielding the canonical lists of bricks and braces is, to be sure, a deep and beautiful theory. However, note that when the graph with which one starts is itself a brick or a brace, the theory provides no further ‘decomposition’. Indeed, at this point we come up against something of a ‘brick wall’! (Of course the pun is intentional!) At present, no theory for further decomposing bricks and braces exists. On the other hand, the following result is known. (See [33].) Theorem 1.6. If G is 2-extendable then G is either a brick or a brace. So what can we say about the structure of 2-extendable graphs? Before we cease posing such questions and start pursuing answers, we note the next two results (the proofs of which can also be found in [33].). Theorem 1.7. If n> 1 and G is n-extendable, then G is (n+ 1)-connected. Theorem 1.8. If n>2 and G is n-extendable, then G is (n- 1)-extendable. For each n > 1, we denote by gE the class of all n-extendable graphs. Then Theorem 1.8 implies that these classes are ‘nested’ as follows: Extending matchings in graphs: A survey 281 Moreover, if we let B denote the class of all bicritical graphs, then Theorems 1.6 and 1.8 imply that if G is not bipartite, the class of bicritical graphs can be included in the nesting: (It is easily seen that all subset containments indicated above are proper.) This leads to our final motivational question. What can one say about the structure of n-extendable graphs? With this question in mind, we now proceed to survey a number of results relating the concept of n-extendability to other well-known graph parameters. 2. Extendability and genus Our interest in matching extendability versus surface embedding began with the following result [35]. Theorem 2.1. No planar graph is 3-extendable. To proceed to the study of extendability on surfaces of higher genus, some notation and a definition are needed. Let C denote a surface, either orientable or nonorientable. Then let p(C) denote the smallest integer such that no graph G embeddable in surface C is ,u(C)-extendable. For example, the dodecahedron is easily seen to be 2-extendable, while by Theorem 2.1 no planar graph is 3-extendable, so it follows that p(sphere) = 3. Recall that the Euler Characteristic of surface C is defined by x(C)=2-2y, when C is orientable and 2-y, when C is not orientable. (Here y denotes the genus of the surface.) The next two results generalize Theorem 2.1 to surfaces of genus > 0. Theorem 2.2. (Plummer [36]). (a) Zf C . 1s an orientable surface with genus y>O, then and if(b) in addition, graph G is triangle-free, G is not (2 +L2& I)-extendable. In a result yet to appear at the time of this writing, Dean [4] has extended the above result in several ways. Theorem 2.3. (a) If C is an orientable surface of genus y > 0, then m=2+L2& 282 M.D. Plummer while (b) if C is nonorientable of genus y > 0, then llW=2+Lfi1. It should be noted that Dean’s results are sharp, i.e. he has proved equality in both cases (a) and (b). In particular, this implies that Dean’s upper bound on n-extendabil- ity of a graph with genus ~J>O is independent of whether or not G is triangle-free. Although Theorem 2.3 significantly extends and improves Theorem 2.2, the proof techniques used for both are very similar. In particular, both proofs make heavy use of what has come to be called the theory of Euler contributions. (For that matter, so did the proof of Theorem 2.1.) Since this approach has proved useful to the author, not only in the area of matching extension, but elsewhere as well [40], we sketch the main ideas. Perhaps some of the readers of this paper will find new ways to exploit it in their own work. The theory of Euler contributions was first studied by Lebesgue [17] and later by Ore [29], as well as by Ore and the author [30]. A well-known result due to Youngs [SO] states that every embedding of a graph G in its surface of minimum orientable genus is 2-cell. It is much less widely known, and to the best of author’s knowledge, was proved for the first time only in 1987 by Parsons et al. [31], that at least one embedding of a graph G in its surface of minimum nonorientable genus is 2-cell. For our purposes, the important fact to be gleaned from this discussion about minimum embeddings is that when a graph is so embedded (orientably or nonorientably), Euler’s formula (i.e. p-q+r =x(Z)) holds. (See [24].) Let v be any point in graph G. The Euler contribution of point v, Q(v), is defined as deg,u deg ” 1 @(u)=l-2+ x_’ c 1 i=l where xi denotes the ‘size’ of the ith face at point v. (i.e. the number of lines in the cycle which forms the boundary of the ith face). The following lemma is clear. Lemma 2.4. If graph G is minimally embedded surface C, then c @(v)=x(C). vet’(G) So it follows immediately that for some point VE V(G), we have Q(v) ax(C)/ j l’(G)I. We call such a point a control point. It may be shown that there are limitations to the types of face configurations which may surround a control point. (Again, for details we refer the reader to [30].) The idea then is to find a partial matching which covers all the neighbors of point v - but not v itself ~ and is of minimum size subject to this covering demand. Obviously, then, such a partial matching cannot extend to a pm, for there is no way to cover the control point v with such an extension. 3. Extendability and claw-free graphs Our next results are of a ‘forbidden’ subgraph nature. In particular, we consider the so-called claw-free graphs. A graph G is said to be claw-free if it contains no induced subgraph isomorphic to the complete bipartite graph K 1, 3 - the so-called ‘claw’. Perhaps, the first deep theorem concerning claw-free graphs was due independently to Minty [25] and Sbihi [42] who showed that in any claw-free graph the independence number (also known as the stability number and the vertex-packing number) can be computed in polynomial time. Since the appearance of this result, studies involving claw-free graphs have appeared in abundance. Part (a) of the following theorem was proved independently by Summer [44] and Las Vergnas [16]; parts (b) and (c) are due to the author [38]. Theorem 3.1. Suppose 1~20 and G is a (2n+ 1)-connected claw-free graph with 1 V(G)1 even. Then: (a) If n = 0, then graph G has a perfect matching; (b) If n= 1, then graph G is a brick (and hence also I-extendable); (c) If n>2, then graph G is n-extendable. This theorem is sharp in the sense that, for all n> 1, we can construct a claw-free graph which is 2n-connected, has an even number of points, but is not n-extendable. Now what about some kind of ‘converse’ to the above theorem? To this end, we have the following result. Let 6(G) denote the minimum degree in G. Theorem 3.2. Suppose n > 1 and that G is a claw-fuee n-extendable graph with 1 V(G)1 even. Then S(G)>2n. The lower bound on 6(G) in Theorem 3.2 is sharp. That is, for each n3 1, we can construct a graph HL which is n-extendable, claw-free and has 6(Hb)=2n. For proofs, constructions and further discussion about extending matchings in claw-free graphs (see [38]). 4. Extendability in products of graphs It was noted sometime in the mists of the past by the author that the 3-cube Q3 is nice example of a small graph which is 2-extendable and bipartite, and hence a brace. In collaboration with Gyiiri [9], we have been able to obtain a rather substantial generalization of this observation. Let G1 and G2 be any two graphs. The Cartesian product of G1 and GZ is denoted by G, x G2 and defined as follows. The point set V(GI x Gz)= {(XI, x2) 1 x1 E V(G,), x2e V(G,)} and two points of the product (x1, x2) and (yl, yZ) are adjacent in the product graph if either x1 =y, and x,y, is a line in G2 or x2=y2 and x,y, is a line in G1. 284 M.D. Plummer Theorem 4.1. Suppose kI and k2 are two nonnegative integers and that the two graphs Gi are ki-extendable, for i= 1,2. Then G1 x G2 is (k, + k2 + I)-extendable. This result is sharp in the following sense. Suppose Gi is ki-extendable for i= 1,2 and suppose deg,, v = kI + 1 and degGl v = k2 + 1. Then deg,, x G2 v = k, + k2 + 2 and hence IC(G~ x G2)6 k, + k2 +2. On the other hand, the product graph G1 x G2 is (k, + k2 + 1)-extendable by the above theorem, and hence by Theorem 1.7, we have K(G~ x GJ3 kI + k2+2. Putting these two inequalities together, we have K(G~ x G2)= k, + kz+2 and hence again by Theorem 1.7, graph G1 x G2 is not (k, + kz + 2)-extendable. 5. Degree sums and neighborhood unions It seems the first so-called degree sum theorems are due to Ore [27,28]. We combine three of his results in the next theorem. Theorem 5.1. If G is a graph with p points such thatfor each pair of nonadjacent points u and V, deg u + deg v > p (respectively, 3 p - 1, 2 p + l), then G has a Hamiltonian cycle (respectively, has a Hamilton path, is Hamiltonian connected). During recent years, there has been a flurry of activity in the area of degree sum studies. (For a sampler of these, see [18].) Note that Ore’s results involve degree sums of sets of two independent points. One of the directions of generalizations which has occurred involves considering the degree sums of sets of i independent points, for t B 3. The next result is a theorem of this type. (See [39] for the proof.) Theorem 5.2. Suppose G is a k-connected graph with p points where p is even and n is any integer satisfying 1 2, G is n-extendable. Theorem 5.2 is sharp in the following sense. Choose n 2 1 and k > 2n. Define a graph H(n, k) consisting of a complete graph on k points each of which is also adjacent to ea