Edge proximity and matching extension in punctured planar triangulations
Edge proximity and matching extension in punctured planar triangulations
复制标题
穿孔平面三角剖分中的边缘邻近度和匹配扩展
DOI：
10.1016/j.disc.2017.07.017
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
J. Fujisawa and A. Saito
中科院分区：
文献类型：
--
作者：
R.E.L. Aldred;J. Fujisawa and A. Saito
图G中的一个匹配M称为可扩的，如果存在G的一个包含M的完美匹配。1989年，证明了每个顶点数至少为8的连通平面图都有一个尺寸为3的匹配，而这个匹配是不可扩的。相比之下，在过去的十年中，当给定的图是5-连通平面三角剖分图或具有很少非三角面的5-连通平面图时，扩展尺寸为3或更大的某些匹配的研究取得了进展。本文证明了：如果G是偶数阶5连通平面图，其中至多有两个面不是三角形，M是大小为4的匹配，其中两条边的两两距离至少为3，则M是可扩的.一个相关的结果，有关完美匹配与禁止的边缘显示。
A matching M in a graph G is said to be extendable if there exists a perfect matching of G containing M. In 1989, it was shown that every connected planar graph with at least 8 vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is 5-connected planar triangulation or 5-connected plane graphs with few non-triangular faces. In this paper, we prove that if G is a 5-connected plane graph of even order in which at most two faces are not triangular and M is a matching of size four in which the edges lie pairwise distance at least three apart, then M is extendable. A related result concerning perfect matching with proscribed edges is shown as well.
登录
查看更多内容
穿孔平面三角测量中的距离匹配
DOI：
10.4310/joc.2016.v7.n2.a15
发表时间：
2016
期刊：
The Journal of Combinatorics
影响因子：
--
作者：
R. Aldred;M. Plummer
通讯作者：
M. Plummer
平面三角剖分中的距离限制匹配扩展
DOI：
10.1016/j.disc.2010.03.027
发表时间：
2010
期刊：
Discret. Math.
影响因子：
--
作者：
R. Aldred;M. Plummer
通讯作者：
M. Plummer
平面三角剖分中的边缘邻近度和匹配扩展
DOI：
--
发表时间：
2004
期刊：
Australas. J Comb.
影响因子：
--
作者：
R. Aldred;M. Plummer
通讯作者：
M. Plummer
平面和投影平面三角剖分中匹配延伸的邻近阈值
影响因子：
0.9
作者：
R. Aldred;M. Plummer
通讯作者：
M. Plummer
环面和克莱因瓶三角剖分中的距离限制匹配扩展
DOI：
10.37236/2952
发表时间：
2014
期刊：
Electron. J. Comb.
影响因子：
--
作者：
R. Aldred;J. Fujisawa
通讯作者：
J. Fujisawa