论文部分内容阅读
设G是一个简单图,具有顶点集合V(G)和边集合E(G)。在连通图G中,如果对任意的v∈V(G),G-v有完美匹配,则称G是因子临界图。一个因子临界图有奇数个顶点且最小度不小于二度。如果对于任意的两个顶点x,y∈V(G),G-x-y都有完美匹配,则称G是二因子临界图。显然G是一个二因子临界图的充分必要条件是(?)v∈V(G),G-v是一个因子临界图。若图G的任意导出子图都不与K1,3同构,则称G是一个无爪图。一个立方图是一个所有顶点都是三度点的图。图的最大匹配计数和完美匹配计数问题是图论和组合最优化中的一个重要分支,它有着广泛的应用。例如,在化学领域,二部图的完美匹配数是[3,4]中所研究的Kekulé结构计数。但是由[2]知:一般图(甚至二部图)的完美匹配计数问题是NP-困难问题,所以最大匹配的计数问题也是困难的。2005年,刘岩刻画了最大匹配数m(G)=|V(G)|+1的因子临界图的结构,本文的第二章在刘岩老师所做的结果的基础上进一步刻画了最大匹配数m(G)=|V(G)|+2的因子临界图的结构。第三章给出了一类特殊图-不含K4-e的无爪立方图的完美匹配数。本文的主要结果如下:Theorem2.10。设G是一个有c个块的因子临界图,则m(G)=|V(G)|+2当且仅当1、除了一个块H1,G的所有其他块是奇圈。其中H1是一个eta图E(l1,l2,l3,l4),满足l1=2,长度为l1的路是G的悬挂路。长度为l4的路的两个端点被G的一条长度为2的悬挂路相连。或者H1是一个theta图Θ(l1,l2,l3),满足l1=4和dG(v1)=dG(v3)=2,此处长度为l1的路是uv1v2v3v。或者2、G中除了两个块H1和H2之外所有块均是奇圈。H1和H2分别是theta图Θ1(l1,l2,l3)和Θ2(l1′,l2′,l3′),满足l1=l1′=2,H1的长度为l1的路和H2的长度为l1′的路均是G的悬挂路。Theorem3.2。设G 2-连通且G是一个不含k4-e的n阶无爪立方图,则n=6k,k≥1为整数,且G的完美匹配数为2k+1。