Microsoft Word - Article.doc


Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè 29, 2007, 66–84. 
 

 
66 
 

 
 
 
 
 

Î вåðøèííîé ïàíöèêëè÷íîñòè íàïðàâëåíнûõ ãðàôîâ ñ 
áîëüøèìè ïîëóñòåïеíÿìè 

 
Ñ. Õ Äàðáèíÿí è È. À Êàðàïåòÿí 

 
Институт проблем информатики и автоматизации НАН  РА  
e-mail: sam_darbin@ipia.sci.am, isko@ipia.sci.am 

 
 

Àííîòàöèÿ 
 

Ïóñòü G  åñòü p -вåðøèííûé ( p ≥13) íàïðàâëåííûé ãðàô ñ 
ìèíèìàëüíèìè ïîëуñòåïеíÿìè, íå ìеíüøèìè, чем ( p -3)/2. Òîãäà äëÿ 
êàæäîãî öåëîãî k , ãäå 3≤ k ≤5 èëè 9≤ k ≤ p -3 ÷åðåç ëþáую âåðøèíу 
ãðàôà G  ïðîõîäèò êîíòóð äëèíû k . 

 
 

 Литература 
 
[1] Ф. Харари, Теория графов, Мир, Москва, 1973. 
[2]  J.Bang-Jensen and G.Gutin, Digraphs. Theory, Algorithms and Applications. 

Springer, 2001. 
[3] Z.M.Song, Pancyclic oriented graphs. J.Graph Theory 18 (1994) 461-468. 
[4] J.Bang-Jensen and Y.Guo, A Note on Vertex Pancyclic Oriented Graphs, 

Odense Universitet, Preprint 20 (1997).  
[5] G.Gutin, Characterizations of Vertex Pancyclic and Pancyclic Ordinary 

Complete Multipartite Digraphs. Discrete Math. 141. (1995)  153-162. 
[6] С.Х. Дарбинян, К.М. Мосесян, О панцикличности регулярных орграфов. ДАН Арм. 

ССР, 1978, т. LXVII,  № 4, 208-211. 
[7] С.Х. Дарбинян, О панцикличности направленных графов с большими 

полустепенями . Математические вопросы кибернетики и вычислительной 
техники. № 14, Ереван (1985) 55-74.  

 
 
 
 
 
 
 
 
 



Ñ. Õ Äàðáèíÿí è È. À Êàðàïåòÿí 
 

67 

Ø»Í ÏÇë³³ëïÇ׳ÝÝ»ñáí áõÕÕáñ¹í³Í ·ñ³ýÝ»ñÇ  
·³·³Ã³ÛÇÝ å³ÝóÇÏÉÇÏáõÃÛ³Ý Ù³ëÇÝ 

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

 
²Ù÷á÷áõÙ 

 

Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ »Ã»  p-·³·³Ã³ÝÇ )13( p     
áõÕÕáõñ¹í³Í G ·ñ³ýÇ ó³Ýϳó³Í ·³·³ÃÇ ÉáÏ³É ÏÇë³³ëïÇ׳ÝÝ»ñÁ ÷áùñ ã»Ý 

2/)3( p  ÃíÇó, ³å³ ó³Ýϳó³Í k, .39  pk  ³ÙµáÕç ÃíÇ Ñ³Ù³ñ, G ·ñ³ýÇ 
Ûáõñ³ù³ÝãÛáõñ ·³·³Ã ·ïÝíáõÙ ¿  k   »ñϳñáõÃÛ³Ý ÏáÕÙÝáñáßí³Í óÇÏÉÇ íñ³: