首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Characterization of a class of graphs related to pairs of disjoint matchings
Authors:Anush Tserunyan
Institution:Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, 0025, Armenia
Abstract:For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the ratio of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that for any graph View the MathML source is the tight upper bound for this ratio. We characterize the class of graphs for which it is precisely View the MathML source. Our characterization implies that these graphs contain a spanning subgraph, every connected component of which is the minimal graph of this class.
Keywords:Matching  Pair of disjoint matchings  Maximum matching
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号