几类图的匹配等价图类

两个图G和H的匹配多项式相等,则称它们匹配等价.用[G]表示图G的所有不同构的匹配等价图的集合.刻画了匹配次大根小于1的图及这些图的补图的匹配等价图类.     

两类图的匹配等价类

完全刻画了Ｐｍ和Ｋ１∪Ｇｍ以及它们的补图的匹配等价图类。     

最大匹配图的围长

将一个图的所有最大匹配作为顶点集,称两个最大匹配相邻,若它们之一通过交换一条边得到另一个,由引所得图为该图的最大匹配图。本文研究了最大匹配图的围长,从而给出了最大匹配图是树或完全图的条件。     

两类新的匹配唯一性图族

本文研究了具有度序列(13,2S-4,3)的图的匹配唯一性,给出了T(1,4,n)∪(s∪i=0Cpi)(n 4)与T(1,5,n)∪(s∪i=0Cpi)(n 5)及其补图匹配唯一的充要条件.     

一类Caterpillars图的匹配刻画

利用匹配多项式的性质以及匹配根的信息研究了图的匹配刻画问题,给出了一类Caterpillars图F（2,m,3）及补图匹配刻画的充分必要条件是m=2,5,8.     

关于图的运算与图的Pfaffian性

关于一般的图的完美匹配计数的问题已证实是NP-hard问题.但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决.由此可见图的Pfaffian性的重要性.在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.     

一个图的匹配数条件

设G是一个简单图,在图G中任意一个最大匹配的基数叫做G的匹配数,记作v(G),在这篇文章中我们获得了下面的结果,(1)设G是连通的和不完全的,则对于x,y∈v(G)和xyE(G),v(G-{x,y}=v(G)-1的充分必要条件是(a)G[A(G)]是完全的和A(G)的每一个点和C(G)的每一个点相邻,(b)c(D(G))=|A(G)| 1,和(c)y∈D(G-x)对于x,y∈C(G)。(2)设G是连通的和不完全的,则v(G-{x,y})=v(G)-2对于x,y∈V(G)和xyE(G)的充分必要条件是GK_(n,n),其中n≥2。     

几类图的匹配唯一性

若图G的匹配多项式为M(G;W),对任何图H,M(G;W)=M(H;W)推出G与H同构,则称G是匹配唯一的.本文讨论了下面的几种图类:(i)B_(m,n,r);(ii)D_(m,n,r);(iii)T_(m,n)的匹配唯一性问题,从而得到一些较为满意的结果.     

图与超图中的彩色匹配综述

超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果.     

具有唯一完美匹配的D-图

为了研究具有完美匹配图的Tuttc集和极端集,文献[1,2]提出了一种新的图运算,并且得到了许多有趣的性质。本文中,我们刻画了level（G）=0的具有唯一完美匹配的饱和图G,并且确定了具有唯一完美匹配图的D-图的边数的紧上界。     

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

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

Recognizing near-bipartite Pfaffian graphs in polynomial time

A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e₁ and e₂ such that G−e₁−e₂ is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.     

On the spectral radii of unicyclic graphs with fixed matching number

In this paper, the first five sharp upper bounds on the spectral radii of unicyclic graphs with fixed matching number are presented. The first ten spectral radii over the class of unicyclic graphs on a given number of vertices and the first four spectral radii of unicyclic graphs with perfect matchings are also given, respectively.     

混和图的特征值分布

建立了混和图的特征值与匹配数、直径以及拟悬挂点数的关系,推广了简单图上若干关于特征值分布的结论.     

The 2-extendability of 5-connected graphs on the Klein bottle

A graph is said to be k-extendable if any independent set of k edges extends to a perfect matching. In this paper, we shall characterize the forbidden structures for 5-connected graphs on the Klein bottle to be 2-extendable. This fact also gives us a sharp lower bound of representativity of 5-connected graphs embedded on the Klein bottle to have such a property, which was considered in Kawarabayashi et al. (submitted for publication) [4].     

On the disjoint paths problem

Using flow and matching algorithms to solve the problem of finding disjoint paths through a given node, and with a technique of Chekuri and Khanna, we give an approximation for the edge-disjoint paths problem in undirected graphs, directed acyclic graphs and directed graphs with edge capacity at least 2.     

Bounding the Size of Equimatchable Graphs of Fixed Genus

A graph G is said to be equimatchable if every matching in G extends to (i.e., is a subset of) a maximum matching in G. In an earlier paper with Saito, the authors showed that there are only a finite number of 3-connected equimatchable planar graphs. In the present paper, this result is extended by showing that in a surface of any fixed genus (orientable or non-orientable), there are only a finite number of 3-connected equimatchable graphs having a minimal embedding of representativity at least three. (In fact, if the graphs considered are non-bipartite, the representativity three hypothesis may be dropped.) The proof makes use of the Gallai-Edmonds decomposition theorem for matchings.      

匹配数为2的图的最小特征值

在所有给定阶数且匹配数为2的连通图中,我们刻画了最小特征值达到极小的图,给出了这类图最小特征值的下界.     

A Vizing-type theorem for matching forests

A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ+ colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ+ colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest.     

匹配最大根小于2的图的匹配等价类

本文刻画了匹配最大根小于2的图及其补图的匹配等价图类。