D:\sbornik\...\Article.DVI


Mathematical Problems of Computer Science 28, 2007, 60{64.

On E dge-Disjoint P air s of M atchings¤

V a h a n V . Mkr t c h ya n y, V a h e L . Mu s o ya n z, A n u s h V . Ts e r u n ya n z

y Institue for Informatics and Automation Problems of NAS of RA
e-mail: vahanmkrtchyan2002@fysu.am, ipia.sci.am, yahoo.comg

z Department of Informatics and Applied Mathematics, Yerevan State University, Armenia
e-mail: vahe musoyan@ysu.am, anush tserunyan@fysu.am, yahoo.comg

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.

Refer ences

[1 ] F. H a r a r y, Gr a p h Th e o r y, A d d is o n -W e s le y, R e a d in g , MA , 1 9 6 9 .

[2 ] F. H a r a r y, M.D . P lu m m e r , " On t h e c o r e o f a g r a p h " , P roc. L ondon M ath. Soc. 17, p p .
3 0 5 -3 1 4 , 1 9 6 7 .

[3 ] L . L o va s z , M.D . P lu m m e r , Ma t c h in g t h e o r y, A n n . D is c r e t e Ma t h . 2 9 , 1 9 8 6 .

[4 ] V . V . Mkr t c h ya n , " On t r e e s wit h a m a xim u m p r o p e r p a r t ia l 0 -1 c o lo r in g c o n t a in in g a
m a xim u m m a t c h in g " , D iscrete M athematics , vo l. 3 0 6 , p p . 4 5 6 -4 5 9 , 2 0 0 6 .

[5 ] V . V . Mkr t c h ya n , " A n o t e o n m in im a l m a t c h in g c o ve r e d g r a p h s " , D iscrete M athematics
, vo l. 3 0 6 , p p . 4 5 2 -4 5 5 , 2 0 0 6 .

[6 ] D . B . W e s t , In t r o d u c t io n t o Gr a p h Th e o r y, P r e n t ic e -H a ll, E n g le wo o d Cli®s , 1 9 9 6 .

¶ñ³ýáõÙ ÁݹѳÝáõñ ÏáÕ ãáõÝ»óáÕ ½áõ·³ÏóáõÙÝ»ñÇ ½áõÛ·»ñÇ Ù³ëÇÝ

ì. ØÏñïãÛ³Ý, ì. ØáõëáÛ³Ý, ². Ì»ñáõÝÛ³Ý

²Ù÷á÷áõÙ

îñí³Í ·ñ³ýÇ Ñ³Ù³ñ ¹Çï³ñÏ»Ýù ÁݹѳÝáõñ ÏáÕ ãáõÝ»óáÕ ½áõ·³ÏóáõÙÝ»ñÇ ·áõÛ·»ñÁ,
áñáÝó ÙdzíáñáõÙÁ å³ñáõݳÏáõÙ ¿ ³Ù»Ý³ß³ï Ãíáí ÏáÕ»ñ, ¨ ¹Çï³ñÏ»Ýù ·ñ³ýÇ
Ù³ùëÇÙ³É ½áõ·³ÏóÙ³Ý Ñ½áñáõÃÛ³Ý Ñ³ñ³µ»ñáõÃÛáõÝÁ ³Û¹åÇëÇ ½áõÛ·»ñáõÙ ³Ù»Ý³ß³ï
ÏáÕ»ñ å³ñáõݳÏáÕ ½áõ·³ÏóÙ³Ý ÑÕáñáõÃÛ³ÝÁ: Ø»Ýù óáõÛó »Ýù ïí»É, áñ 5/4-Á ×Çßï í»ñÇÝ
·Ý³Ñ³ï³Ï³Ý ¿ ³Ûë ѳñ³µ»ñáõÃÛ³Ý Ñ³Ù³ñ:

¤The authors are supported by a grant of the Armenian National Science and Educational Fund

6 0