کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648878 | 1342434 | 2010 | 19 صفحه PDF | دانلود رایگان |
A graph GG is said to have property E(m,n)E(m,n) if it contains a perfect matching and for every pair of disjoint matchings MM and NN in GG with |M|=m|M|=m and |N|=n|N|=n, there is a perfect matching FF in GG such that M⊆FM⊆F and N∩F=0̸N∩F=0̸. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n)E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0)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)E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.
Journal: Discrete Mathematics - Volume 310, Issue 20, 28 October 2010, Pages 2618–2636