D:\sbornik\...\article_eng.DVI


Mathematical Problems of Computer Science 30, 25{30, 2008.

On E xistence of Cer tain Locally-balanced 2-par tition

of a T r ee

S u r e n V . B a likya n

Yerevan State University

email: suren.balikyan@gmail.com

Abstract

A necessary and su±cient condition is obtained for the problem of such partitioning
of the set of vertices of a tree G into two disjoint sets V1 and V2, such that for given
sets V 01 µ V (G) and V 02 µ V (G) (V 01 \ V 02 = ;) it satis¯es the conditions V 01 µ V1,
V 02 µ V2 and jj¸(v) \ V1j ¡ j¸(v) \ V2jj · 1 for any vertex v of G, where ¸(v) is the set
of all vertices of G adjacent to v.

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
lo 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 g r a p h s G wit h ¢ ( G ) = 3 " , R eports of NAS
R A, Applied M athematics, vo l. 1 0 5 , n u m . 1 , p p . 2 1 { 2 7 , 2 0 0 5 .

[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
lo 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 g r 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 athemat-
ics, vo l. 1 0 6 , n u m . 3 , p p . 2 1 8 { 2 2 6 , 2 0 0 6 .

[3 ] S .V . B a likya n , " On lo c a lly-b a la n c e d 2 -p a r t it io n s o f s o m e b ip a r t it e g r a p h s " , Abstracts
of papers of 15th International Conference "M ATHE M ATICS. COM P UTING. E D U-
CATION.", vo l. 1 5 , p . 7 , D u b n a , R u s s ia , Ja n u a r y 2 8 - Fe b r u a r y 0 2 2 0 0 8 .

[4 ] F. H a r a r y, Graph Theory, A d d is o n -W e s le y, R e a d in g , MA , 1 9 6 9 .

[5 ] C. B e r g e , Graphs and Hypergraphs, E ls e vie r S c ie n c e L t d , 1 9 8 5 .

̳éÇ ÉáϳÉ-ѳí³ë³ñ³Ïßéí³Í áñáß³ÏÇ 2-ïñáÑÙ³Ý ·áÛáõÃÛ³Ý Ù³ëÇÝ

ê.ì. ´³ÉÇÏÛ³Ý

²Ù÷á÷áõÙ

êï³óí³Í ¿ ³ÝÑñ³Å»ßï ¨ µ³í³ñ³ñ å³Ûٳݪ G ͳéÇ ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛ³Ý V1
¨ V2 ãѳïíáÕ »Ýóµ³½ÙáõÃÛáõÝÝ»ñÇ ³ÛÝåÇëÇ ïñáÑÙ³Ý ·áÛáõÃÛáõÝÁ å³ñ½»Éáõ ѳٳñ,

2 5



2 6 On Existence of Certain Locally-balanced 2-partition of a Tree

áñ ïñí³Í V 01 µ V ( G) ¨ V 02 µ V ( G ) ( V 01 \ V 02 = ;) µ³½ÙáõÃÛáõÝÝ»ñÇ Ñ³Ù³ñ µ³í³ñ³ñí»Ý
Ñ»ï¨Û³É å³ÛÙ³ÝÝ»ñÁ. V 01 µ V1, V 02 µ V2 ¨ ͳéÇ Ûáõñ³ù³ÝãÛáõñ v ·³·³ÃÇ Ñ³Ù³ñ
ï»ÕÇ áõݻݳ Ñ»ï¨Û³É ³Ýѳí³ë³ñáõÃÛáõÝÁ jj (̧ v ) \ V1j ¡ j (̧ v ) \ V2jj ¸ 1 , áñï»Õ ¸ ( v ) -áí
Ý߳ݳÏí³Í ¿ v-ÇÝ ÏÇó ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛáõÝÁ: