D:\sbornik\...\new.DVI


Mathematical Problems of Computer Science 29, 2007, 104{106.

On Simultaneous 2-locally-balanced 2-par tition for

T wo For ests with Same Ver tices

H o vik G. Ta n a n ya n y a n d R a fa ye l R . K a m a lia n z

y Russian-Armenian State University
e-mail: HTananyan@yahoo.com,

zYerevan State University
e-mail: rrkamalian@yahoo.com

Abstract

The existence of a partition of the common set of the vertices of two forests into two
subsets, when di®erence of their capacities in the neighbourhood of each vertex of each
forest is not greater than 2 is proved, and an example, which shows that improvement
of the speci¯ed constant is impossible is brought.

Refer ences

[1 ] S .V . B a likya n , R .R . K a m a lia n , On N P -c o m p le t e n e s s o f t h e P r o b le m o f E xis t e n c e o f
L o c a lly-b a la n c e d 2 -p a r t it io n fo r B ip a r t it e Gr a p h s G wit h ¢ ( G ) = 3 , R eports of NAS
R A, Applied M athematics , v. 1 0 5 , N 1 , 2 0 0 5 , p p . 2 1 -2 7 . ( In R u s s ia n .)

[2 ] S . V . B a likya n , R . R . K a m a lia n , On N P -c o m p le t e n e s s o f t h e P r o b le m o f E xis t e n c e
o f L o c a lly-b a la n c e d 2 -p a r t it io n fo r B ip a r t it e Gr a p h s G wit h ¢ ( G ) = 4 u n d e r t h e
E xt e n d e d D e ¯ n it io n o f t h e N e ig h b o u r h o o d o f a V e r t e x, R eports of NAS R A, Applied
M athematics , v. 1 0 6 , N 3 , 2 0 0 6 , p p . 2 1 8 -2 2 6 . ( In R u s s ia n .)

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

[4 ] D . d e W e r r a , B a la n c e d S c h e d u le s , INF OR J . , 9 ( 3 ) , 1 9 7 1 , p p . 2 3 0 -2 3 7 .

¶³·³ÃÝ»ñÇ Ñ³ÙÁÝÏÝáÕ µ³½ÙáõÃÛáõÝÝ»ñáí »ñÏáõ ³Ýï³éÝ»ñÇ
ÙdzųٳݳÏÛ³ 2-ÉáϳÉ-ѳí³ë³ñ³Ïßéí³Í 2-ïñáÑÙ³Ý Ù³ëÇÝ

Ð. ¶. ³ݳÝÛ³Ý ¨ è. è. ø³Ù³ÉÛ³Ý

²Ù÷á÷áõÙ

²å³óáõóí³Í ¿, áñ ·³·³ÃÝ»ñÇ Ñ³ÙÁÝÏÝáÕ µ³½ÙáõÃÛáõÝÝ»ñ áõÝ»óáÕ »ñÏáõ
³Ýï³éÝ»ñÇ Ñ³Ù³ñ ·áÛáõÃÛáõÝ áõÝÇ Ýñ³Ýó ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛ³Ý ³ÛÝåÇëÇ ïñáÑáõÙ
»ñÏáõ »Ýóµ³½ÙáõÃÛáõÝÝ»ñÇ, áñÇ ¹»åùáõÙ Ûáõñ³ù³ÝãÛáõñ ³Ýï³éÇ Ûáõñ³ù³ÝãÛáõñ
·³·³ÃÇ ßñç³Ï³ÛùáõÙ ³Û¹ »ñÏáõ »Ýóµ³½ÙáõÃÛáõÝÝ»ñÇ ï³ññ»ñÇ ù³Ý³ÏÝ»ñÇ ï³ñµ»-
ñáõÃÛáõÝÁ ãÇ ·»ñ³½³ÝóáõÙ 2-Á, ¨ ³Û¹ ѳëï³ïáõÝÁ ÷áùñ³óÝ»É Ñݳñ³íáñ ã¿:

1 0 4