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


Mathematical Problems of Computer Science 30, 31{35, 2008.

On E xistence of 2-par tition of a T r ee, Which Obeys

the Given P r ior ity

S u r e n V . B a likya n y, 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 such partitioning
of the set of vertices of a tree G into two disjoint sets V1 and V2, which, for a given
function p : V (G) ! f¡1; 0; 1g with some special restriction, satis¯es the condition
j¸(v) \ V1j ¡ j¸(v) \ V2j = p(v) ¢ (jfvg \ V1j ¡ jfvg \ V2j) 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 ve r t e x" , R eports of NAS R A, Applied M athematics,
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 UCA-
TION.", 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 .

3 1



3 2 On Existence of 2-partition of a Tree, Which Obeys the Given Priority

̳éÇ ³ÛÝåÇëÇ 2-ïñáÑÙ³Ý ·áÛáõÃÛ³Ý Ù³ëÇÝ,
áñÁ »ÝóñÏíáõÙ ¿ ïñí³Í ݳ˳å³ïíáõÃÛ³ÝÁ

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

²Ù÷á÷áõÙ

êï³óí³Í ¿ ³ÝÑñ³Å»ßï ¨ µ³í³ñ³ñ å³ÛÙ³Ý G ͳéÇ ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛ³Ý V1
¨ V2 ãѳïíáÕ »Ýóµ³½ÙáõÃÛáõÝÝ»ñÇ ³ÛÝåÇëÇ ïñáÑÙ³Ý ·áÛáõÃÛáõÝÁ å³ñ½»Éáõ ѳٳñ,
áñ ïñí³Í ѳïáõÏ ë³Ñٳݳ÷³ÏáõÙÝ»ñáí ýáõÝÏódzÛÇ Ñ³Ù³ñ µ³í³ñ³ñíÇ Ñ»ï¨Û³É
å³ÛÙ³ÝÁ p : V ( G ) ! f¡ 1 ; 0 ; 1 g ͳéÇ Ûáõñ³ù³ÝãÛáõñ v ·³·³ÃÇ Ñ³Ù³ñ j (̧ v ) \V1j¡j¸ ( v ) \
V2j = p( v ) ¢ ( jfvg \ V1j ¡ jfvg \ V2j ) , áñï»Õ ¸ ( v ) -áí Ý߳ݳÏí³Í ¿ v-ÇÝ ÏÇó ·³·³ÃÝ»ñÇ
µ³½ÙáõÃÛáõÝÁ: