D:\sbornik\...\article.DVI


Mathematical Problems of Computer Science 24, 2005, 86{88.

On I nter val E dge Color ings of H ar ar y Gr aphs H 2 n¡ 2 ; 2 n
¤

R a fa ye l R . K a m a lia n , P e t r o s A . P e t r o s ya n

Institute for Informatics and Automation Problems of NAS of RA

e-mail rrkamalian@yahoo.com, pet petros@yahoo.com

Abstract

The problems of existence and construction of interval edge colorings of Harary
graphs H2n¡2;2n are investigated. Bounds are found for the possible number of colors
in interval edge colorings of H2n¡2;2n.

Refer ences

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

[2 ] M.N .S . S wa m y, K . Th u la s ir a m a n , Gr a p h s , N e t wo r ks a n d A lg o r it h m s , Jo h n W ile y &
S o n s , N e w Y o r k, 1 9 8 1 .

[3 ] D .B . W e s t , 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, N e w Je r s e y, 2 0 0 1 .

[4 ] R .R . K a m a lia n , In t e r va l E d g e Co lo r in g s o f Gr a p h s , D o c t o r a l d is s e r t a t io n , N o vo s ib ir s k,
1 9 9 0 .

[5 ] R .R . K a m a lia n , P .A . P e t r o s ya n , On lo we r b o u n d fo r W ( K2n ) , Ma t h e m a t ic a l P r o b le m s
o f Co m p u t e r S c ie n c e , V o l. 2 3 , Y e r e va n , 2 0 0 4 , p p .1 2 7 -1 2 9 .

¤The work was partially supported by 04.10.31 Target Program of RA.

8 6



R.R. Kamalian, P.A. Petrosyan 8 7

ʳé³ñÇÇ H2n-2,2n ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ Ý»ñÏáõÙÝ»ñÇ Ù³ëÇÝ

è.è. ø³Ù³ÉÛ³Ý, ä.². ä»ïñáëÛ³Ý

²Ù÷á÷áõÙ

¸Çï³ñÏí³Í »Ý ʳé³ñÇÇ H2n¡2;2n ·ñ³ýÝ»ñÇ ÙÇç³Ï³Ûù³ÛÇÝ ÏáÕ³ÛÇÝ Ý»ñÏáõÙÝ»ñÇ
·áÛáõÃÛ³Ý ¨ ϳéáõóÙ³Ý Ñ³ñó»ñ, ¨ ëï³óí³Í »Ý ·Ý³Ñ³ï³Ï³ÝÝ»ñ ³Û¹ Ý»ñÏáõÙÝ»ñáõÙ
û·ï³·áñÍíáÕ ·áõÛÝ»ñÇ Ñݳñ³íáñ ÃíÇ Ñ³Ù³ñ: