Distance-restricted matching extension in planar triangulations |
| |
Authors: | R.E.L. Aldred Michael D. Plummer |
| |
Affiliation: | a Department of Mathematics and Statistics, University of Otago, P.O. Box 56, Dunedin, New Zealand b Department of Mathematics, Vanderbilt University, Nashville, TN, 37240, USA |
| |
Abstract: | A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension. |
| |
Keywords: | Distance-restricted matching Planar triangulation |
本文献已被 ScienceDirect 等数据库收录! |
|