Papua New Guinea | Download APK | The Vault

On restricted matching extension in planar graphs

On restricted matching extension in planar graphs

Discrete Mathematics 231 (2001) 73–79 www.elsevier.com/locate/disc On restricted matching extension in planar graphs R.E.L. Aldreda , Michael D. Plu...

85KB Sizes 2 Downloads 19 Views

Discrete Mathematics 231 (2001) 73–79

www.elsevier.com/locate/disc

On restricted matching extension in planar graphs R.E.L. Aldreda , Michael D. Plummerb; ∗ a Department

of Mathematics and Statistics, University of Otago, P.O. Box 56, Dunedin, New Zealand of Mathematics, Vanderbilt University, Nashville, TN 37240, USA

b Department

Received 14 July 1999; revised 20 April 2000; accepted 7 August 2000

Abstract Let G be a connected graph with at least 2(m + n + 1) vertices. Then G is E(m; n) if for each pair of disjoint matchings M; N ⊆ E(G) of size m and n, respectively, there exists a perfect matching F in G such that M ⊆ F and F ∩ N = ∅. In the present paper, we wish to study the property E(m; n) for the various values of integers m and n when the graphs in question are restricted to be planar. It is known (Plummer, Annals of Discrete Mathematics 41 (1989) 347–354) that no planar graph is E(3; 0). This result is improved in the present paper by showing that no planar graph is E(2; 1). This severely limits the values of m and n for which a planar graph can have property E(m; n) and leads us to consider the properties E(1; n) and E(0; n) c 2001 for certain classes of planar graphs. Sharpness of the various results is also explored.  Elsevier Science B.V. All rights reserved.

1. Introduction In this paper all graphs will be ;nite and, unless otherwise speci;ed, simple as well. Moreover, since this is a paper concerned with perfect matchings in graphs, we will assume that all graphs under consideration have an even number of vertices unless otherwise speci;ed. Let G be a connected graph with at least 2(m + n + 1) vertices. Graph G is said to be E(m; n) if for every pair of disjoint matchings M; N ⊆ E(G) of size m and n, respectively, there is a perfect matching F in G such that M ⊆ F and F ∩ N = ∅. If G is E(m; 0), we say that G is m-extendable. (A graph with a perfect matching will be said to be E(0; 0).) In fact, it was the concept of m-extendability which subsequently gave rise to the more general property E(m; n). Graphs which are m-extendable have been studied quite extensively. (See the surveys [8] and [9].) Some of the early results on this family of graphs can also be found in the book [4] where their connection with other areas of matching theory is discussed. ∗

Corresponding author. Tel.: +1-6153226668; fax: +1-6153430215. E-mail addresses: [email protected] (R.E.L. Aldred), [email protected] (M.D. Plummer). c 2001 Elsevier Science B.V. All rights reserved. 0012-365X/01/$ - see front matter  PII: S 0 0 1 2 - 3 6 5 X ( 0 0 ) 0 0 3 0 5 - 8

74

R.E.L. Aldred, M.D. Plummer / Discrete Mathematics 231 (2001) 73–79

The ;rst paper to treat the more general concept of E(m; n) was due to Porteous and the ;rst author Porteus and Aldred [10]. Their paper focussed on when the implication E(m; n) → E(p; q) does and does not hold. In [7] Plummer showed that no planar graph is E(3; 0). Our main result in Section 2 strengthens this result by showing that no planar graph is even E(2; 1). This result, taken together with the lattice of implications of [14], limits the values of m and n for which a planar graph can be E(m; n) to E(2; 0), E(1; n) and E(0; n) for certain n. As the property E(2; 0) in planar graphs has already been widely studied (see for example [1,2]) we will concentrate on E(1; n) and E(0; n). In Section 3, general planar graphs with connectivity restrictions are considered. It is shown that, while a 3-connected planar graph need not even be E(0; 0) (i.e., need not even have a perfect matching), a 4-connected planar graph must be E(1; 1) and E(0; n), for n63, and a 5-connected planar graph must be E(1; n), for n62, and E(0; n), for n64. 2. No planar graph is E(2; 1) The proof of the following theorem proceeds in a fashion very similar to that of Theorem 3.3 of [7]; hence, only an outline is presented here. Theorem 2.1. No planar graph is E(2; 1). Proof: We shall assign an ordered n-tuple (x1 ; : : : ; x n ) to each vertex v of degree n in the planar graph G if the faces incident with vertex v have sizes x1 ; : : : ; x n (in some order). Furthermore, we shall agree to write these n-tuples in monotone non-decreasing order and we shall say that the associated vertex is of type (x1 ; : : : ; x n ). We shall also say that a vertex v has a type bounded by (y1 ; : : : ; yn ) if v has type (x1 ; : : : ; x n ) and for each i; i = 1; : : : ; n; xi 6yi . The so-called theory of Euler contributions was initiated by Lebesgue in 1940 [3] and further developed by Ore in 1967 [5] and by Ore and Plummer in 1969 [6]. A corollary of this study says that in a plane graph of minimum degree at least 3, there must exist a vertex v the type of which is bounded by at least one of the following types: deg v = 3: (3; 6; x); x = 6; : : : (3; 7; x); x = 7; : : : ; 41 (3; 8; x); x = 8; : : : ; 23 (3; 9; x); x = 9; : : : ; 17 (3; 10; x); x = 10; : : : ; 14 (3; 11; x); x = 11; 12; 13 (4; 4; x); x = 4; : : : (4; 5; x); x = 5; : : : ; 19 (4; 6; x); x = 6; : : : ; 11 (4; 7; x); x = 7; 8; 9

R.E.L. Aldred, M.D. Plummer / Discrete Mathematics 231 (2001) 73–79

(5; 5; x); (5; 6; x); deg v = 4: (3; 3; 3; x); (3; 3; 4; x); (3; 3; 5; x); (3; 4; 4; x); deg v = 5: (3; 3; 3; 3; x);

75

x = 5; : : : ; 9 x = 6; 7 x = 3; : : : x = 4; : : : ; 11 x = 5; 6; 7 x = 4; 5 x = 3; 4; 5:

Such a vertex v will be called a control vertex. We will show that for any plane graph with a control vertex type bounded by any of the above, one can always select two independent edges e1 and e2 and a third edge f such that the graph cannot contain a perfect matching which includes e1 and e2 , but not f. First, let control vertex v have degree 3 and suppose it has type bounded by (3; 6; x). In fact, we will assume that v has type (3; 6; x). The proof for the other types bounded by (3; 6; x) are done similarly. Let the three neighbors of v be denoted by u1 ; u2 and u3 in clockwise order. Without loss of generality, we may assume that the triangular face at v is denoted by vu1 u2 and that the hexagonal face at v is denoted vu2 abcu3 . Let edge u1 u2 be denoted by e1 and let e2 be the edge cu3 . Finally, let f denote the edge vu3 . Then it is clear that there is no perfect matching of G which includes e1 and e2 , but not f. Similar arguments apply to all other cases when the control vertex has degree 3. Now suppose control vertex v has degree 4 and that its four neighbors are u1 ; u2 ; u3 and u4 clockwise. Let us consider the type (3; 3; 4; x). It should be noted that here the actual clockwise order of the faces might be such that the face size sequence (clockwise) is either 3; 3; 4; x or perhaps 3; 4; 3; x. First suppose the order to be 3; 3; 4; x and that the two triangles at v are u1 u2 v and u2 u3 v, respectively. Let the 4-face at v be denoted u3 wu4 v. Then letting e1 = u2 u3 , e2 = wu4 and f = u1 v, we see that there is no perfect matching containing e1 and e2 , but not f. Now suppose the clockwise order of the faces at v is 3; 4; 3; x and that the two triangular faces at v are u1 u2 v and u3 u4 v. Let e1 = u1 u2 , e2 = u3 u4 and let f denote any other edge in G. Again, no perfect matching of the type required can exist. Other cases where the control vertex has degree 4 follow similarly. Finally, if the control vertex v has degree 5, let the neighbors of v in clockwise order be u1 ; u2 ; u3 ; u4 and u5 and suppose the four triangular faces at v are u1 u2 v; u2 u3 v; u3 u4 v and u4 u5 v. Let e1 = u1 u2 ; e2 = u3 u4 and let f = vu5 . Again no perfect matching of the type required can exist. Corollary 2.2. No planar graph is E(3; 0). Proof: By Corollary 3:1 of Porteous and Aldred [10], property E(3; 0) implies property E(2; 1). As mentioned earlier, planar graphs can be E(2; 0) and such graphs have been extensively studied. Here we shall concern ourselves with the properties E(1; n) and

76

R.E.L. Aldred, M.D. Plummer / Discrete Mathematics 231 (2001) 73–79

E(0; n). To see that there are planar graphs which are E(1; n) and E(0; n) for arbitrary non-negative integers n, consider the following family of graphs. Let n be a non-negative integer and de;ne the graph Gn to be the graph with vertex set V (Gn ) = {x0 ; x1 ; : : : ; x2n+1 } ∪ {y0 ; y1 ; : : : ; y2n+1 } and edge set E(Gn ) = {xi xi+1 : 06i62n + 1} ∪ {yi yi+1 : 06i62n + 1} ∪ {xj yj : 06j62n + 1} ∪ {xj yj+1 : 06j62n + 1} where addition of subscripts is modulo 2n + 2. Theorem 2.3. The graph Gn is E(1; n ) for each 06n 6n. Proof: Let {e; f1 ; f2 ; : : : ; fn } ⊆ E(Gn ) be such that F = {f1 ; f2 ; : : : ; fn } forms a matching with e ∈ F. Then, without loss of generality, we may assume that e is either x0 x1 or x0 y0 . First, let us suppose that e = x0 x1 . By symmetry, we may assume that y0 y1 ∈ F (since only one of y0 y1 and y1 y2 can be in F). Now V (Gn ) − {x0 ; x1 ; y0 ; y1 } can be covered by n 4-cycles x2 x3 y3 y2 ; x4 x5 y5 y4 ; : : : ; x2n x2n+1 y2n+1 y2n . In each of these 4-cycles, there can be at most two edges from F and, since F is an independent set of edges, there are two edges not in F which together cover all four of the vertices in the 4-cycle. Two such edges from each of these 4-cycles together with x0 x1 and y0 y1 gives a perfect matching for Gn which includes e and avoids F. So we may assume that e = x0 y0 . Let r be the smallest positive integer such that x2r+1 y2r+1 ∈ F. Note that there must be such an r6n − 1 as there are at most n edges in F. Let M = {x0 y0 } ∪ {xi xi+1 ; yi yi+1 : 16i62r − 1} ∪ {x2r+1 y2r+1 }. To extend M to the desired perfect matching of Gn , cover V (Gn ) − V (M ) with 4-cycles and choose appropriate edges not in F as in the previous case. This completes the proof. Corollary 2.4. The graph Gn is E(0; n ) for each 06n 6n. In the light of Theorem 2.3 and Corollary 2.4 above, we see that there are planar graphs with the E(1; n) and E(0; n) properties for each non-negative integer n. At the other end of the spectrum, there are planar graphs, with an even number of vertices, which do not even admit perfect matchings. For example, the complete bipartite graphs K2; 2k are planar and even, but admit no perfect matching for k = 1. Thus, we cannot hope to prove further extendability properties for planar graphs without restrictions stronger than simply having an even number of vertices. In the next section, we shall investigate more closely the relationship between the E(m; n) property and connectivity in even planar graphs.

3. E(m; n) and connectivity In the plane, we are restricted to graphs which are at most 5-connected and in this section we investigate the extendability guaranteed when we restrict our even planar graphs by connectivity alone.

R.E.L. Aldred, M.D. Plummer / Discrete Mathematics 231 (2001) 73–79

77

The complete bipartite graphs K2; 2k , as mentioned earlier, are not E(0; 0) and have connectivity 2. There are 3-connected planar graphs which admit no perfect matching as well. Among these are the so-called Kleetopes which may be constructed as follows. Let {w; x; y; z} be the vertices of a plane K4 . Subdivide the edge wx by inserting an even number of new vertices (¿ 0) on the edge and then triangulate this subdivision by making each new vertex adjacent to both y and z. Consider the vertices of T , the triangulation constructed so far, to be white. Now add a new black vertex inside each of the faces of T and triangulate. The resulting graph is planar, 3-connected and has an even number of vertices. As long as the subdivision in the construction is non-trivial, there are more black vertices than white and, since each black vertex has only white neighbors, there can be no perfect matching. Thus our ;rst result focuses on 4-connected planar graphs of even order. Theorem 3.1. Let G be a 4-connected planar graph on an even number of vertices. Then G is E(1; 1). Proof: Suppose to the contrary that G is such a graph and that we have edges e; f ∈ E(G) such that there is no perfect matching in G which uses the edge e and which avoids the edge f. That is, the graph G  = G − V (e) − {f} contains no perfect matching. By Tutte’s theorem there is a set S ⊆ V (G  ) such that G  − S has ¿|S| + 2 odd components. Consider a graph G ∗ obtained from G via G  as follows. Contract to single vertices those subgraphs of G corresponding to odd components of G  − S and delete those vertices of G corresponding to vertices in even components of G  − S. Suppress any multiple edges formed in this process (i.e. if on contracting a subgraph of G we get a pair of vertices joined by more than one edge, remove all but one of those edges). Now delete from this graph the edges e and f, as well as all edges in S and between vertices in S and V (e), so that G ∗ is a bipartite planar graph with bipartition (B; W ), where B = S ∪ V (e) and W denotes the set of ¿|S| + 2 vertices {c1 ; : : : ; c } resulting from the contraction of the odd components C1 ; : : : ; C , respectively. Since G is 4-connected, there are at least 4 edges incident with each vertex of W in G ∗ ∪ {f} and hence there are at least 4 − 2 edges from vertices in W to vertices of B in G ∗ . However, G ∗ is bipartite and planar so that we have at most 2( + (|S| + 2)) − 4 = 2( + |S|) edges in total. Thus, 4 − 262 + 2|S|; 2 62|S| + 2: But ¿|S| + 2 so that we have 2|S| + 462|S| + 2; which is a contradiction. That this result is sharp is indicated by the following graph $1 . Let $1 have vertex set V ($1 ) = {w; x0 ; x1 ; x2 ; x3 ; y0 ; y1 ; y2 ; y3 ; z} and edge set E($1 ) = {wxi ; xi xi+1 ; yi yi+1 ;

78

R.E.L. Aldred, M.D. Plummer / Discrete Mathematics 231 (2001) 73–79

xi yi ; zyi : 06i63} with addition of subscripts modulo 4. The graph $1 so de;ned is 4-connected (and 4-regular) planar and even, but is not E(1; 2). It is easy to construct from $1 an in;nite family of graphs with these properties. Corollary 3.2. Let G be a 5-connected planar graph on an even number of vertices. Then G is E(1; 2). Proof: Let G be such a graph and let {e; f1 ; f2 } ⊆ E(G) with {f1 ; f2 } independent. Now, G  = G − f2 is 4-connected planar and of even order. By Theorem 3.1, G  is E(1; 1) and hence admits a perfect matching which contains e and avoids f1 . This induces a perfect matching on G which includes e and avoids both f1 and f2 . Since e; f1 and f2 were chosen arbitrarily, subject to {f1 ; f2 } forming an independent set and {e} ∩ {f1 ; f2 } = ∅, G is E(1; 2). We note that the graph $2 formed by taking two copies of the icosahedron, deleting one vertex from each copy and then joining the two resulting graphs in planar fashion by a ;ve edge matching between the vertices of degree 4, is 5-connected (and 5-regular), planar and even, but is not E(1; 3). This illustrates the sharpness of Corollary 3.2. Theorem 3.3. Let G be a 4-connected planar graph on an even number of vertices. Then G is E(0; 3). Proof: Suppose to the contrary that G is as in the statement of the theorem and that F = {f1 ; f2 ; f3 } ⊆ E(G) is a set of three independent edges in G such that G − F contains no perfect matching. Thus there is a set S ⊆ V (G) such that G  = G − F − S has at least |S| + 2 odd components. By Theorem 3.1, G is E(1; 1) and hence by Theorem 3:2 of Porteous and Aldred [10] is also E(0; 2) so that G − {f1 ; f2 } does contain a perfect matching. From this, we may conclude that G  has precisely |S|+2 odd components. Now, as in the proof of Theorem 3.1, form G ∗ from G via G  as follows. Contract to single vertices those subgraphs of G corresponding to odd components of G  and delete those vertices of G corresponding to vertices in even components of G  . Suppress any multiple edges formed in this process (i.e. if on contracting a subgraph of G we get a pair of vertices joined by more than one edge, remove all but one of those edges). Now delete from this graph the edges f1 ; f2 and f3 , as well as all edges in S so that G ∗ is a bipartite planar graph with bipartition (B; W ), where B = S and W denotes the set of |S|+2 vertices resulting from the contraction of the odd components. Since G is 4-connected, each of the odd components in G  is joined to the rest of G by at least four edges. In G ∗ this means that there are at least 4(|S| + 2) − 6 = 4|S| + 2 edges from vertices corresponding to odd components in G  to vertices in S. But G ∗ is planar and bipartite on 2|S| + 2 vertices, so it can contain at most 2(2|S| + 2) − 4 = 4|S| edges. This contradiction completes the proof.

R.E.L. Aldred, M.D. Plummer / Discrete Mathematics 231 (2001) 73–79

79

The graph $1 above is 4-connected planar and even but not E(0; 4) so we see that Theorem 3.3 is also sharp. Corollary 3.4. Let G be a 5-connected planar graph on an even number of vertices. Then G is E(0; 4). Proof: Let G be as in the statement of the corollary and let F ={f1 ; f2 ; f3 ; f4 } ⊆ E(G) be an independent set of edges. Now G − f1 is 4-connected planar and even, so by Theorem 3.3 contains a perfect matching avoiding {f2 ; f3 ; f4 }. Such a matching induces a perfect matching in G avoiding F. This completes the proof. The sharpness of this result is shown by $2 which is 5-connected planar and even, but not E(0; 5). We cannot hope to replace connectivity hypotheses above with analogous edgeconnectivity hypotheses as we can easily adapt the Kleetopes to form 5-edge-connected even planar graphs (in fact, triangulations) which are not E(0; 0). Replacing each of the black vertices in the Kleetope with a copy of the vertex deleted icosahedron, and suitably triangulating produces the desired result. References [1] D.A. Holton, D.-J. Lou, M.D. Plummer, On the 2-extendability of planar graphs, Discrete Math. 96 (1991) 81–99. [2] D.A. Holton, M.D. Plummer, 2-extendability in 3-polytopes, Combinatorics, Eger, Hungary, 1987, Colloquim Mathematics Socretatis JanLos Bolyai, Vol. 52, AkadLemiai KiadLo, Budapest, 1988, pp. 281–300. [3] H. Lebesgue, Quelques consLequences simples de la formule d’Euler, J. de Math. 9 (1940) 27–43. [4] L. LovLasz, M.D. Plummer, Matching Theory, Ann. Discrete Math. 29, North-Holland, Amsterdam, 1986. [5] O. Ore, The Four-Color Problem, Academic Press, New York, 1967, pp. 54 – 61. [6] O. Ore, M.D. Plummer, Cyclic colorations of plane graphs, in: W.T. Tutte (Ed.), Recent Progress in Combinatorics, Academic Press, New York, 1969, pp. 287–293. [7] M.D. Plummer, A theorem on matchings in the plane, Ann. Discrete Math. 41 (1989) 347–354. [8] M.D. Plummer, Extending matchings in graphs: a survey, Discrete Math. 127 (1994) 277–292. [9] M.D. Plummer, Extending matchings in graphs: an update, Congr. Numer. 116 (1996) 3–32. [10] M.I. Porteous, R.E.L. Aldred, Matching extensions with prescribed and forbidden edges, Austral. J. Combin. 13 (1996) 163–174.