On Edge-Disjoint Pairs of Matchings

Authors

  • Vahan V. Mkrtchyan Institute for Informatics and Automation Problems of NAS RA
  • Vahe L. Musoyan Yerevan State University
  • Anush V. Tserunyan Yerevan State University

Abstract

For a given graph consider the pairs of edge-disjoint matchings whose union contains as many edges as possible, and consider the relation of the cardinality of a maximum matching to the cardinality of the largest matching among such pairs. We show that 5=4 is a tight upper bound for this relation.

References

F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

F. Harary, M.D. Plummer, "On the core of a graph", Proc. London Math. Soc. 17, pp. 305-314, 1967.

L. Lovasz, M.D. Plummer, Matching theory, Ann. Discrete Math. 29, 1986.

V.V. Mkrtchyan, "On trees with a maximum proper partial 0-1 coloring containing a maximum matching", Discrete Mathematics, vol. 306, pp. 456-459, 2006.

V.V. Mkrtchyan, "A note on minimal matching covered graphs", Discrete Mathematics, vol. 306, pp.452-455, 2006.

D.B. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, 1996.

Downloads

Published

2021-12-10

How to Cite

Mkrtchyan, V. V. ., Musoyan, V. L. ., & Tserunyan, A. V. . (2021). On Edge-Disjoint Pairs of Matchings. Mathematical Problems of Computer Science, 28, 60–64. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/502

Issue

Vol. 28 (2007): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.