特殊图类X-%2cA-与基本极大(m%2b1)K-%2c2--free图.pdf

河南大学硕士学位论文 摘 要 摘 要：八十年代以来，图的匹配理论在组合数学，运筹学与控制论 中的作用日益突出，近年来更成为图论及组合最优化中最为活跃的研究课题 之一。而图的导出匹配是近年来兴起的新研究方向。G的匹配M是导 出匹配，如果f51 的一个最大导出匹配的边数。是否存在一个非完伞连通简单图G，对于图 是一个有趣而且基本的问题。谢炎涛已经解决了这个问题，找到了顶点数 位12， 13，14个点的导出匹配数为1的满足上述条件的图。本文研究了 一个特殊图类托，定义此={H：H=(VE)是一个简单连通图，任给 V∈V 托中图的结构性质，对特殊图类‰的研究内容与基本极大(m+1)鲍一free 图的结构研究有直接联系。另外，本文还研究基本极大2K2一丘ee图的一些 特征，并构造了一些顶点数为14，15，16基本极大2K2-free图。 关键词： 导出匹配；导出匹配数；特殊图类XA；极大2K2一free图；基 本极大(m+1)K2-free图。 河南大学硕士学位论文 Abstract Since has an 1980s，grapematchingtheryplaydeincreasingprominent roleinthecombinationof and mathematics，operationscontorytheory， inthe has recent becomeoneofthemostactivecoreissues especially years，it with the of andcombination． dealing optimizationGraphmatchingtheory Meanwhile hasbeenanewresearch exportmatching directions developed inthe M isinduced G if pastyears．Amatchingof induced numberof thenumberof G，denoted matching byIM(G)，is ofamaximuminduced ofG． isthereaconnectedbut edges matching not thatforeach of completesimplegraphG，such pair nonadjacent verticesXand 7．This isfundamental problem y，IM(G+xy)=IM(G)-4-1 and seniorschoolmate very yan-tao has soveldthe interesti