|
|||||
|
|
On edge-disjoint pairs of matchings |
|
| Authors: | V.V. Mkrtchyan V.L. Musoyan A.V. Tserunyan |
| Affiliation: | a Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, 0025, Armenia b Institute for Informatics and Automation Problems of National Academy of Sciences of Armenia, 0014, Armenia c Department of Mathematics, University of California, LA, United States |
| Abstract: | For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for |M|/|H|. |
| Keywords: | Matching Maximum matching Pair of edge-disjoint matchings |
| 本文献已被 ScienceDirect 等数据库收录！ | |