Edge proximity and matching extension in planar triangulations
Edge proximity and matching extension in planar triangulations
复制标题
平面三角剖分中的边缘邻近度和匹配扩展
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
M. Plummer
中科院分区：
文献类型：
--
作者：
R. Aldred;M. Plummer
设G是一个至少有2（m + n + 1）个顶点的图.则G是E（m，n），如果对于每对分别为m和n的不相交匹配M，N <$E（G），存在G中的完美匹配F使得M <$F和F <$N =<$.在本文中，我们希望研究的性质E（m，n）的各种值的整数m和n时，所讨论的图被限制为平面。已知没有平面图是E（3，0）或E（2，1）。在本文中，我们表明，在平面甚至三角剖分，匹配的大小为3满足一定的邻近条件可以扩展到完美匹配。我们还精确地确定当所涉及的图是平面的偶三角剖分或近三角剖分时，对于m和n的哪些值，性质E（m，n）成立。
Let G be a graph with at least 2(m + n + 1) vertices. Then G is E(m, n) if for each pair of disjoint matchings M, N ⊆ E(G) of size m and n respectively, there exists a perfect matching F in G such that M ⊆ F and F ∩N = ∅. In the present paper we wish to study property E(m, n) for the various values of integers m and n when the graphs in question are restricted to be planar. It is known that no planar graph is E(3, 0) or E(2, 1). In this paper we show that in planar even triangulations, matchings of size three satisfying certain proximity conditions can be extended to perfect matchings. We also determine precisely for which values of m and n, the property E(m, n) holds when the graphs involved are even triangulations or near-triangulations of the plane.