Distance-restricted matching extension in planar triangulations
Distance-restricted matching extension in planar triangulations
复制标题
平面三角剖分中的距离限制匹配扩展
DOI：
10.1016/j.disc.2010.03.027
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Plummer
中科院分区：
文献类型：
--
作者：
R. Aldred;M. Plummer
一个图G称为具有性质E（m，n），如果它包含一个完美匹配，并且对于G中的每一对不相交匹配M和N，|M| =m并且|N| =n，则G中存在完美匹配F使得M <$F和N <$F=0 <$。在以前的论文（Aldred and Plummer 2001）[2]中，对嵌入平面的图的性质E（m，n）进行了研究。特别地，虽然没有平面图是E（3，0），但证明了如果三条边之间的距离至少为2，则它们总是可以扩展为完美匹配。在本文中，我们扩展这些结果考虑的属性E（m，n）的平面三角剖分时，更一般的距离限制的边缘被包括和避免在扩展。
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.