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


Mathematical Problems of Computer Science 31, 116{121, 2008.

N ecessar y and Su±cient Condition for E xistence of

Locally-balanced 2-par tition of a T r ee under the

E xtended De¯nition of a N eighbour hood of a Ver tex

S u r e n V . B a likya n y a n d R a fa ye l R . K a m a lia n z

y Yerevan State University
e-mail: suren.balikyan@gmail.com

z Russian-Armenian State University
e-mail: rrkamalian@yahoo.com

Abstract

A necessary and su±cient condition is obtained for the problem of partitioning of
the set of vertices of a tree G into two disjoint sets V1 and V2 such that it satis¯es the
condition jj¸(v) \ V1j ¡ j¸(v) \ V2jj · 1 for any vertex v of G, where ¸(v) is the set of
all vertices of G the distance of which from v does not exceed 1.

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, 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
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, 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 L o 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 Gr a p h s " , Abstracts
of papers of 15th International Conference "M athematics. Computing. E ducation.", 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 .

1 1 6



S. Balikyan and R. Kamalian 1 1 7

̳éáõÙ ÉáϳÉ-ѳí³ë³ñ³Ïßéí³Í 2-ïñáÑÙ³Ý ·áÛáõÃÛ³Ý Ñ³Ù³ñ
³ÝÑñ³Å»ßï ¨ µ³í³ñ³ñ å³ÛÙ³Ý ·³·³ÃÇ ßñç³Ï³ÛùÇ ÁݹɳÛÝí³Í

ë³ÑÙ³ÝÙ³Ý ¹»åùáõÙ

ê. ´³ÉÇÏÛ³Ý, è. ø³Ù³ÉÛ³Ý

²Ù÷á÷áõÙ

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