【作者】 张薏佩；

【导师】 原晋江； 王秀梅；

【作者基本信息】 郑州大学 ， 运筹学与控制论， 2013， 硕士

【摘要】 匹配理论是图论的主要研究专题之一,并且与其他理论课题具有密切联系.鉴于n-可扩图、导出匹配可扩图、PM-紧邻图的研究工作,我们提出两个新的概念：圈唯一可扩图和导出圈可扩图.称图G是圈唯一可扩图,如果对于图G的每一个偶圈C,G-V(C)有唯一的完美匹配.称图G是圈可扩图,如果去掉G的任意一个偶圈的顶点后得到的图有完美匹配.称图G是导出圈可扩图,如果去掉G的任意一个导出偶圈的顶点后得到的图有完美匹配.这里图G的一个圈C是导出圈,如果V(C)的导出子图是一个圈.显然,如果一个图是圈可扩图,那么它是导出圈可扩图.反之未必成立.称图G是一个K3,3的H-培分,如果G≠K3,3但是G可由K3,3把它的一个哈密顿圈上的一些边换成奇路得到.用(?)来表示所有满足下面两个条件的图的集合：(i)G是极大外平面二部图；(ii)如果C为G的外部面的边界,那么C中恰有两条22-边(两个端点在G中的度均为2)且它们不相邻,C中其余的边为23-边(一个端点在G中的度大于等于3,另一个端点在G中的度为2).本文我们主要研究圈唯一可扩二部图和导出圈可扩图,主要得到了下面的结果：·图G是一个圈唯一可扩哈密顿二部图当且仅当G是K3,3或者G是(?)中的图的支撑哈密顿子图或者G是K3,3的H-部分；.圈唯一可扩的一般二部图的部分刻画，●一个图是导出圈可扩图的度和及最小度条件.更多还原

【Abstract】 Matching theory is one of the important special topics of graph theory and is in connection with other theoretic problems closely. Motivated by the study of n-extendable graphs,IM-extendable graphs, and PM-compact graphs, we propose two new notions: cycle uniquely extendable graph and induced-cycle extendable graph. We say that a graph G is cycle uniquely extendable if G-V(C) has a unique perfect matching for any even cycle of G. We say that a graph G is cycle-extendable if G-V(C) has a perfect matching for any even cycle C of G. We say that a graph G is induced-cycle extendable if G-V(C) has a perfect matching for any induced even cycle C of G. Here, a cycle C of graph G is called an induced cycle if G[V(C)] is a cycle of G. Obviously, if a graph is cycle extendable, it is induced-cycle extendable. The converse is not true.A graph G is called an H-subdivision of K3,3if G≠K3,3, but G can be obtained from K3,3by replacing some edges in a Hamilton cycle of K3,3by odd paths. Let (?) denote the set of all the graphs G which satisfy the following two conditions:(i) G is a maximal outerplane bipartite graph;(ii) if C is the boundary of the outer face of G, then C has only two22-edges (each of its two ends has degree2in G), which are not adjacent, the remaining edges of C are23-edges (in.G,one end of such edge has degree2and the other end has degree at least3).In this paper, we study cycle uniquely extendable graphs and induced-cycle extend-able graphs. The main results are the following:·A Hamiltonian bipartite graph G is cycle uniquely extendable if and only if G is K3,3or an H-subdivision of K3,3or a spanning Hamiltonian subgraph of the graph in (?);·Partial characterizations of general bipartite graphs which are cycle uniquely ex-tendable;·The conditions of a graph to be induced-cycle extendable.更多还原