D:\sbornik\...\Aritcle.DVI


Mathematical Problems of Computer Science 24, 2005, 104{106.

A N ote on M atching Cover ed Gr aphs

V a h a n V . Mkr t c h ya n

Department of Informatics and Applied Mathematics, Yerevan State University

e-mail vahanmkrtchyan2002yahoo.com

Abstract

A graph is called matching covered if for its every edge there is a maximum matching
containing it. It is shown that line-extremal matching covered graphs contain a perfect
matching.

Refer ences

[1 ] H a r a r y F., 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 ] L o va s z L ., P lu m m e r M.D ., Ma t c h in g Th e o r y, A n n a ls o f D is c r e t e Ma t h . 2 9 , N o r t h
H o lla n d , 1 9 8 6 .

[3 ] W e s t D . B ., 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 .

¶ñ³éáõÙ ½áõ·³ÏóáõÙÝ»ñáí ͳÍÏí³Í ·ñ³ýÝ»ñÇ Ù³ëÇÝ

ì.ì. ØÏñïãÛ³Ý

²Ù÷á÷áõÙ

¶ñ³ýÁ ÏáãíáõÙ ¿ ½áõ·³ÏóáõÙÝ»ñáí ͳÍÏí³Í, »Ã» Ýñ³ ó³Ýϳó³Í ÏáÕÇ
ѳٳñ ·áÛáõÃÛáõÝ áõÝÇ ³ÛÝ å³ñáõݳÏáÕ Ù³ùëÇÙ³É ½áõ·³ÏóáõÙ: òáõÛó ¿ ïñí»É,
áñ ½áõ·³ÏóáõÙÝ»ñáí ͳÍÏí³Í ·ñ³ýÝ»ñÁ, áñáÝù ¿ùëïñ»Ù³É »Ý ÏáÕÇ Ñ»é³óáõÙ
·áñÍáÕáõÃÛ³Ý Ýϳïٳٵ, å³ñáõݳÏáõÙ »Ý ϳï³ñÛ³É ½áõ·³ÏóáõÙ:

1 0 4