论文部分内容阅读
八十年代以来,图的匹配理论在组合数学,运筹学与控制论中的作用日益突出,近年来更成为图论及组合最优化中最为活跃的研究课题之一。而图的导出匹配是近年来兴起的新研究方向。G的匹配M是导出匹配,如果[5]E(V(M))=M。图G的导出匹配数IM(G)表示图G的一个最大导出匹配的边数。是否存在一个非完全连通简单图G,对于图G的任意两个非相邻顶点x和y,都有IM(G+xy)=IM(G)+17这是一个有趣而且基本的问题。谢炎涛已经解决了这个问题,找到了顶点数位12,13,14个点的导出匹配数为1的满足上述条件的图。本文研究了一个特殊图类XA,定义XA={H:H=(V,E)是一个简单连通图,任给v∈V IM(H)=IM(H--N(v)),任给ab∈E,N(a)--N(b)≠0).将研究X中图的结构性质,对特殊图类XA的研究内容与基本极大(m+1)K2-free图的结构研究有直接联系。另外,本文还研究基本极大2K2-free图的一些特征,并构造了一些顶点数为14,15,16基本极大2K2-free图。