Proximity thresholds for matching extension in planar and projective planar triangulations
Proximity thresholds for matching extension in planar and projective planar triangulations
复制标题
平面和投影平面三角剖分中匹配延伸的邻近阈值
DOI：
10.1002/jgt.20511
复制
发表时间：
2011
影响因子：
0.9
通讯作者：
M. Plummer
中科院分区：
文献类型：
--
作者：
R. Aldred;M. Plummer
一个至少有2(m+1)个顶点且有完美匹配的图称为m-可扩图，如果给定任何匹配M且|M|=m，则G中有一个完美匹配F使得M⊆F。最近，至少有2m+2个顶点的图被定义为距离dm-可扩展的，如果给定任何匹配M且其边位于成对距离至少d处，则存在包含M的完美匹配。
A graph on at least 2(m + 1) vertices with a perfect matching is said to be m‐extendable if, given any matching M with |M| = m, there is a perfect matching F in G such that M⊆F. It has been known for some time that no planar graph is 3‐extendable. More recently, a graph on at least 2m+ 2 vertices has been defined to be distance d m‐extendable if given any matching M with |M| = min which the edges lie at pair‐wise distance at least d, there is a perfect matching containing M.