论文部分内容阅读
图的匹配可扩理论是图论中研究的主要问题之一.对导出匹配可扩图的研究来源于导出匹配及完美匹配的研究.Plummer[7]于1980年首先提出了n可扩的概念，随后同年[3]他又研究了关于n可扩的一些性质.1998年原晋江教授[1]对此作了一个变形，提出导出匹配可扩图的概念，并得到结论：如果图G是含有2n个点的连通的导出匹配可扩图，那么｜E(G)｜≥3n-2，当且仅当G≌T×K2时取等号，其中T为含有n个点的树.经验证图T×K2的围长为4.2005年，周菊[6]给出了含有2n个点、3n-1条边的导出匹配可扩图只能为T×K2+e.经验证图T×K2+P的围长为4.而围长为3时的导出匹配可扩图的边数的下界还是个未解问题.本文解决了这个问题，并得到了以下结论： 定理1若G是一个含有2n个顶点、围长为3的导出匹配可扩图，那么｜E(G)｜≥3n.而且这个界是紧的。 本文首先给出了满足上面这个界的几个特殊的导出匹配可扩图。 定理2设G是一个含有2n个顶点、3n条边且围长为3的导出匹配可扩图。如果δ(G)≥3，那么G≌K4或者G≌C3×K2。 定理3设G是一个含有2n个顶点、3n条边且围长为3的导出匹配可扩图。如果图G只有一个2度点，那么G=H1或者G=H2。 定理4设G是一个含有2n个顶点、3n条边且围长为3的导出匹配可扩图.如果图G含有两个或两个以上2度点并且这些2度点互不相邻，那么G≌H3或者G≌H4或者G≌H5。 然后构造出所有边数达到下界且围长为3的导出匹配可扩图.即在定理2、定理3、定理4中给出的七个图上适当加若干条3长的悬挂路可构造出所有图。