共查询到17条相似文献,搜索用时 93 毫秒
1.
2.
几类图的匹配多项式之间的关系与一类图的匹配等价图 总被引:1,自引:0,他引:1
张海良 《纯粹数学与应用数学》2007,23(2):178-182
研究了几类图的匹配多项式以及它们之间的一些整除关系,给出了路的匹配多项式相互整除的一个充分必要条件,并且刻画了图T2,2,n的所有匹配等价图. 相似文献
3.
几类图的匹配等价图类 总被引:1,自引:0,他引:1
魏岭 《数学的实践与认识》2011,41(17)
两个图G和H的匹配多项式相等,则称它们匹配等价.用[G]表示图G的所有不同构的匹配等价图的集合.刻画了匹配次大根小于1的图及这些图的补图的匹配等价图类. 相似文献
4.
匹配最大根小于等于2的图的匹配等价 总被引:2,自引:0,他引:2
给出了十六个匹配等价桥,证明了两个匹配最大根小于等于2的图匹配等价当且仅当它们之间可以由这十六个匹配等价桥进行等价转换,完整地刻画了这些图的补图的匹配等价图类,找到了这些图和它们的补图中的所有匹配唯一图. 相似文献
5.
6.
目前我们已知的极大导出匹配可扩图只有Kn,n和K2n.为了研究它们是否是仅有的极大导出匹配可扩图,我们考虑了匹配数,导出匹配数,极大导出匹配可扩图以及一个相关的猜想,并得出了若干相关的结果. 相似文献
7.
8.
9.
一类Caterpillars图的匹配刻画 总被引:1,自引:0,他引:1
申世昌 《纯粹数学与应用数学》2010,26(4):541-545
利用匹配多项式的性质以及匹配根的信息研究了图的匹配刻画问题,给出了一类Caterpillars图F(2,m,3)及补图匹配刻画的充分必要条件是m=2,5,8. 相似文献
10.
11.
12.
A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005 相似文献
13.
《Journal of Graph Theory》2018,89(1):55-63
A matching M in a graph G is uniquely restricted if there is no matching in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs. 相似文献
14.
Domingos M. Cardoso 《Journal of Global Optimization》2001,21(1):91-106
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. 相似文献
15.
Domingos M. Cardoso 《Journal of Global Optimization》2001,19(3):291-306
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. 相似文献
16.
V.V. Mkrtchyan 《Discrete Mathematics》2006,306(4):452-455
A graph is called matching covered if for its every edge there is a maximum matching containing it. It is shown that minimal matching covered graphs without isolated vertices contain a perfect matching. 相似文献
17.
Alberto Alexandre Assis Miranda Cláudio Leonardo Lucchesi 《Discrete Applied Mathematics》2010,158(12):1275-1278
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 e1 and e2 such that G−e1−e2 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. 相似文献