单圈图的邻接矩阵的分类及其最大行列式

一个单圈图G的邻接矩阵是奇异的当且仅当G含完美匹配和4m(m∈N)阶圈，或G和从G中删去唯一圈中的顶点及其关联边后得到的导出子图均不含完美匹配．单圈图的邻接矩阵的最大行列式是4．     

图的匹配与拉普拉斯特征值

设G=(V(G),E(G))是一个图,M是E(G)的—个子集.如果M中任意两条边均无公共端点,则称M为图G的匹配.如果图G的一个匹配M中的边恰好关联G的每一个顶点,则称M为图G的完美匹配.如果图G中除了一个顶点以外,其他所有顶点都与匹配M中的边相关联,则称M为图G的几乎完美匹配.如果对任意v∈V(G), G-v均有完美匹配,则称G是因子临界的.本文中,我们给出了判定一个图有完美匹配、或者几乎完美匹配或者是因子临界的拉普拉斯谱条件.     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。     

具有｜V（G）｜＋2个最大匹配的因子临界图G^＊

在连通图G中,如果对任意的V∈V(G),G-v有完美匹配,则称G是因子临界图.该文刻画了具有|V(G)| +2个最大匹配的因子临界图.进而,刻画了一些特殊的双因子临界图.     

二部图上完美匹配的正交匹配分解

给定简单二部图G=（V，E），最大度是k（k≥3），G有一个完美匹配M={e1，e2，…，ek}。称边集E的划分{E1，E2，…，El}是G的一个关于肼的正交匹配分解，如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G，存在关于完美匹配肼的正交匹配分解，并给出了求这个分解的多项式时间算法。     

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性

给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的.     

导出匹配可扩图的局部运算

称图G为导出匹配图可扩的（简称为IM－可扩的），如果图G的一每个导出匹配都包含在G的一个完美匹配中，本给出了导出匹配可扩图的一些局部运算。     

偶匹配可扩性的极图问题(英文)

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.     

偶匹配可扩性的极图问题

设G是含有完美匹配的简单图. 称图G是偶匹配可扩的(BM-可扩的), 如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配. 极图问题是图论的核心问题之一. 本文将刻画极大偶匹配不可扩图, 偶图图类和完全多部图图类中的极大偶匹配可扩图.     

关于n-连通图的完美匹配与最大匹配

ξ1.引言本文所考虑的图均指无自环、无重边、无向有限的连通图,没有特别指明的术语见[1].以V(G)、E(G)分别表示图C的顶点集与边集. 设M是图G的一个支撑子图.若M的每个顶点的度是0或者1,则称M是G的一个匹配,若M是G的匹配中边数最多的一个,则称M是G的一个最大匹配;若M是G的匹配,且M中无0度顶点,则称M是G的一个完美匹配. 图G称为n连通的,若对G的任意两个不同的顶点x,y,G中存在n条以x,y为端点     

导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性

图Ｇ的一个匹配Ｍ是导出的,若Ｍ是图Ｇ的一个导出子图。图Ｇ是导邮匹配可扩的（简记ＩＭ－可扩的）,若图Ｇ的任一导出匹配均含于图Ｇ的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图Ｇ以及一个正整数ｒ,确定是否存在图Ｇ的一个导出匹配Ｍ使得Ｍ≥ｒ”是ＮＰ－完全的。⑵对直径为２的图以及直径为３的偶图,问题“确定一个给定图是否为导出匹配可扩的”是ＣＯ－ＮＰ完全的;而对完全多部图而言,问题“     

Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.     

INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS

It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 which has the same parity as |V(G)|, G-I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The k-th power of G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G3 and T(G) (the total graph of G) are ID-factor-critical, and G4 (when |V(G)| is even) is strongly IM-extendable; if G is 2-connected, then D2 is ID-factor-critical.     

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

Forcing matching numbers of fullerene graphs

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.     

Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.     

Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.