Form from gby deleting and reinserting the edges

AUSTRALASIAN JOURNAL OF COMBINATORICS Volume 29 (2004), Pages 215–224

Edge proximity and matching extension in planar

Department of Mathematics
Vanderbilt University
Nashville, Tennessee 37240
U.S.A.

Abstract

E(3, 0) and more recently in [1], this result was strengthened to show that no planar graph is even E(2, 1). In the present paper we determine precisely those values of m and n for which the property E(m, n) holds for planar triangulations. In addition, we will present a first result dealing with the extension of matchings in which the edges are sufficiently far apart pairwise. Examples are also given to show that the results presented are best possible in several senses. For a general background on matching in graphs, the reader is referred to [3].

2 Doubly independent edge sets

Let us assume first that H is connected. We form a connected spanning subgraph

e1 e2 e3

Figure 2.1

Thus, to complete the proof we need only show that s ≥ 3 (and hence t ≥ 5). Hence suppose s ≤ 2.

Each such odd component has at least 5 neighbours in K forming a separating cycle As we noted earlier, S ̸= ∅ so there are at least three odd components in G − K.

e3

tices in which the indicated edges form a doubly independent set of size four which cannot be extended to a perfect matching. (In Figure 2.2 note that it is understood that where two edges appear to meet there is vertex of G − (V (F) ∪ S).)

3 E(m, n) and Regularity

so that we are unable to exceed the extendability properties guaranteed by Plesn´ık, even when we add planarity to our hypotheses.

In [1], it was shown that 4-connected planar graphs are E(1, 1) and 5-connected planar graphs are E(1, 2). Both of these results were shown to be best possible via 4-regular, and 5-regular, examples respectively. Consequently, we cannot hope to gain by adding 4-regularity or 5-regularity to our hypotheses.

Figure 3.2

construction again in this paper, we name this graph, G∗, the bipartite distillation of G based on {e}, {f1, f2, f3} and S.)
Since G is 5-connected, there are at least 5 edges incident on each vertex of W in G∗∪ {f1, f2, f3} and hence there are at least 5σ − 6 = 5|S| + 4 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|) = 4|S| + 4 edges in total. Thus |S| = 0. This indicates that G − V (e) has two odd components C1 and C2 joined by a matching formed by the edges f1, f2, f3. But G has at most one non-triangular face so this structure is impossible and the result follows. □

= icosahedron − vertex

e

Theorem 3.4 Let G be a 5-connected planar triangulation on an even number of vertices. Then G is E(0, 7).

Proof. Let G be as in the hypothesis of the theorem. We then know that G is E(1, 3) by Corollary 3.2 and so E(0, 4) by Theorem 3.2 of [9]. But then by Theorem 2.7 of [9], G is also E(0, 3), E(0, 2), E(0, 1) and E(0, 0). Now let k be the smallest integer such that G is E(0, k), but not E(0, k + 1). (If there is no such k, we are done.) So there exists a set of k + 1 independent edges F = {f1, . . . , fk+1} ⊆ E(G) and a set S ⊆ V (G) such that G − F − S has |S| + 2 odd components C1, . . . , C|S|+2 and each fi joins two different Ci’s. As before, choose S to a smallest such set. Form G∗, the bipartite distillation as defined above, based upon ∅, F and S, and denote by ci the vertex resulting from the shrinking of odd component Ci, for i = 1, . . . , |S|+2. Let W = {c1, . . . , cs+2}.

222 R.E.L. ALDRED AND M.D. PLUMMER

= icosahedron − vertex

|S| + 2 − (k + 1) + ˆφ = 2.

That is,
ˆφ = k + 1 − |S|. (2)

From (1) and (3) we get

k + 1 ≤ 2|S| ≤ 4k − 16

Proof of claim: Suppose v is a vertex of degree 1 in ˆG. Let φ1, φ2, φ3 be the faces of ˆG and suppose, without loss of generality, that v lies in the boundary of φ1. Then

MATCHING EXTENSIONS IN THE PLANE 223

If all faces in a plane graph G are bounded by 4-cycles, then we say that G is a quadrangulation. Similarly, a pentagonalization is a plane graph in which all faces are bounded by 5-cycles. It is a straightforward consequence of Euler’s formula that no quadrangulation or pentagonalization can be 4-connected. In Figures 3.5 and 3.6 we have examples of 3-connected quadrangulations and pentagonalizations which are not E(0, 0). Note that the quadrangulation shown in Figure 3.5 is also bipartite with an equicardinal bipartition. Consequently, these higher degrees of face regularity cannot guarantee enhanced extendability properties without additional restrictions beyond connectivity.

224 R.E.L. ALDRED AND M.D. PLUMMER

[1] R.E.L. Aldred and M.D. Plummer, On restricted matching extension in planar graphs, Discrete Math., 231 (2001), 73–79.

[2] Dingjun Lou, N-extendability of graphs, Ph.D. Thesis, University of Otago, 1992.

[7] M.D. Plummer, Extending matchings in graphs: a survey, Discrete Math., 127 (1994), 277–292.

[8] M.D. Plummer, Extending matchings in graphs: an update, Congressus Nu- mer., 116 (1996), 3–32.