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


Mathematical Problems of Computer Science 25, 2006, 9{11.

An I nequality Related to the P air s of M atchings of a

Gr aph

R a fa ye l R . K a m a lia n * , V a h a n V . Mkr t c h ya n * *

*Institute for Informatics and Automation Problems of NAS RA
*Department of Informatics and Applied Mathematics, Yerevan State University

e-mails rrkamalian@yahoo.com, vahanmkrtchyan2002@yahoo.com

Abstract

For a given graph disjoint pairs of matchings the union of which contains as many
edges as possible are considered. It is shown that the relation of the cardinality of a
maximum matching to the cardinality of the largest matching in those pairs does not
exceed 3=2. A conjecture is posed which states that this coe±cient can be replaced by
5=4 . Finally, a family of graphs is presented which shows that the abovementioned
coe±cient can not be replaced by a constant which is smaller than 5=4.

R eferences

[1 ] 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 u 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 306, 2 0 0 6 , p p . 4 5 5 -4 5 8 .

[2 ] 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 .

[3 ] 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. 1 7
( 1 9 6 7 ) , 3 0 5 -3 1 4 .

[4 ] L . L o va s z , M. D . P lu m m e r , Ma t c h in g Th e o r y, Annals of D iscrete M ath. 2 9 , N o r t h
H o lla n d , 1 9 8 6 .

[5 ] 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, In c .,1 9 9 6 .

¶ñ³ýáõÙ ½áõ·³ÏóáõÙÝ»ñÇ ½áõÛ·»ñÇÝ ³éÝãíáÕ ÙÇ ³Ýѳí³ë³ñáõÃÛ³Ý Ù³ëÇÝ

è. ø³Ù³ÉÛ³Ý, ì. ØÏñïãÛ³Ý

²Ù÷á÷áõÙ

¸Çï³ñÏí»É »Ý ·ñ³ýÇ ãѳïíáÕ ½áõ·³ÏóáõÙÝ»ñÇ ³ÛÝ ½áõÛ·»ñÁ, áñáÝó ÙdzíáñáõÙÁ
å³ñáõݳÏáõÙ ¿ Ñݳñ³íáñÇÝ ã³÷ ß³ï ÏáÕ: òáõÛó ¿ ïñí»É, áñ ·ñ³ýÇ Ù³ùëÇÙ³É

9



1 0 An Inequality Related to the Pairs of Matchings of a Graph

½áõ·³ÏóÙ³Ý Ñ½áñáõÃÛ³Ý Ñ³ñ³µ»ñáõÃÛáõÝÁ ³Û¹ ½áõÛ·»ñáõÙ ³Ù»Ý³ß³ï Ãíáí ÏáÕ»ñ
å³ñáõݳÏáÕ ½áõ·³ÏóÙ³Ý Ñ½áñáõÃÛ³ÝÁ ãÇ ·»ñ³½³ÝóáõÙ 3/2-Á: ²é³ç³ñÏí»É ¿ í³ñϳÍ,
ѳٳӳÛÝ áñÇ ³Ûë ·áñͳÏÇóÁ ϳñ»ÉÇ ¿ ÷á˳ñÇÝ»É 5/4-áí: ¶ïÝí»É ¿ ·ñ³ýÝ»ñÇ ÙÇ
ÁÝï³ÝÇù, áñÁ óáõÛó ¿ ï³ÉÇë, áñ áñù³Ý ¿É Ù»Í ÉÇÝÇ ·ñ³ýÁ, í»ñáÑÇßÛ³É ·áñͳÏÇóÁ
Ñݳñ³íáñ ã¿ ÷á˳ñÇÝ»É 5/4-Çó ÷áùñ Ãíáí: