Extending matchings in planar graphs V |
| |
Authors: | Michael D. Plummer |
| |
Affiliation: | Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA |
| |
Abstract: | A graph G on at least 2n + 2 vertices in n-extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges e1 and e2 are such that the removal of their endvertices leaves at least one odd component Co. The subgraph G[V(Co) V(e1) V(e2)] is called a generalized butterfly (or gbutterfly). Clearly, a 2-extendable graph can contain no gbutterfly. The converse, however, is false. We improve upon a previous result by proving that if G is 4-connected, locally connected and planar with an even number of vertices and has no gbutterfly, it is 2-extendable. Sharpness with respect to the various hypotheses of this result is discussed. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|