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 is the tight upper bound for this ratio. We characterize the class of graphs for which it is precisely . 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 等数据库收录! |
|