D:\sbornik\...\333.DVI


Mathematical Problems of Computer Science 33, 35{40, 2010.

A N ote on Shor t P aths in Or iented Gr aphs

S a m ve l K h . D a r b in ya n a n d Is ka n d a r A . K a r a p e t ya n

Institute for Informatics and Automation Problems of NAS of RA
e-mail: samdarbin@ipia.sci.am, isko@ipia.sci.am

Abstract

Let G be an oriented graph of order p ¸ 3 and minimum semi-degrees at least
[p=2] ¡ k for a positive integer k. For a subset C of vertices G, we obtain su±cient
conditions implying that for any pair of distinct vertices x; y 2 V (G) ¡ C there is a
path from x to y of length less than a given integer which does not contain the vertices
of C.

Refer ences

[1 ] J. B a n g -Je n s e n a n d G. Gu t in , D ig r a p h s . Th e o r y. A lg o r it h m s a n d A p p lic a t io n s , S p r in g e r ,
2 0 0 0 .

[2 ] J. D . U llm a n , Co m p u t a t io n a l A s p e c t s o f V L S I,Co m p u t e r S c ie n c e P r e s s , 1 9 8 4 .

àõÕÕáñ¹í³Í ·ñ³ýÝ»ñáõ٠ϳñ× ×³Ý³å³ñÑÝ»ñÇ Ù³ëÇÝ

ê. ¸³ñµÇÝÛ³Ý ¨ Æ. γñ³å»ïÛ³Ý

²Ù÷á÷áõÙ

¸Çóáõù G-Ý p- ·³·³Ã³ÝÇ (p ¸ 3 ) áõÕÕáñ¹í³Í ·ñ³ý ¿, áñÇ ·³·³ÃÝ»ñÇ
ÏÇë³³ëïÇ׳ÝÝ»ñÁ ÷áùñ ã»Ý [p= 2 ] ¡ k ÃíÇó (áñï»Õ k ¸ 1 ¨ ³ÙµáÕç ÃÇí ¿), ¨ ¹Çóáõù
C-Ý G ·ñ³ýÇ ·³·³ÃÝ»ñÇ áñ¨> »Ýóµ³½ÙáõÃÛáõÝ ¿: Ü»ñϳ ³ß˳ï³ÝùáõÙ ëï³óí³Í
»Ý µ³í³ñ³ñ å³ÛÙ³ÝÝ»ñ, áñáÝó ¹»åùáõÙ G ·ñ³ýÇ ó³Ýϳó³Í »ñÏáõ ï³ñµ»ñ x ¨ y
·³·³ÃÝ»ñÇ Ñ³Ù³ñ ·áÛáõÃÛáõÝ áõÝÇ C µ³½ÙáõÃÛ³Ý ·³·³ÃÝ»ñáí ã³ÝóÝáÕ ¨ ïñí³Í ÃíÇó
÷áùñ »ñϳñáõÃÛ³Ùµ x -Çó ¹áõñë »ÏáÕ ¨ y-Á ÙïÝáÕ ÏáÕÙÝáñáßí³Í ׳ݳå³ñÑ:

3 5