Microsoft Word - Gayane.doc


Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè 31, 90--99, 2008. 

 
90 
 

 
 
 

Î äëèííûõ êîíòóðàõ â íàïðàâëåííûõ ãðàôàõ, 
ïðîõîäÿùèõ ÷åðåç äàííó þ âåðøèíó 

 
Ñàìâåë Õ. Äàðáèíÿí  è  Èñêàíäàð À. Êàðàïåòÿí 

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

 
Аннотация 

 
Ïóñòü G  åñòü )12( n -âåðøèííûé ( n ≥6) íàïðàâëåííûé ãðàô ñ 

ìèíèìàëüíûìè ïîëуñòåïеíÿìè, íå ìеíüøèìè  1n . Äîêàçûâàåòñÿ, ÷òî 
÷åðåç ëþáую âåðøèíу òàêîãî ãðàôà  ïðîõîäèò êîíòóð äëèíû .2n  

 
   

 
Литература 
 
[1] Ф. Харари, Теория графов, Мир, Москва, 1973. 
[2] J. Bang-Jensen and G. Gutin, Digraphs. Theory. Algorithms and Applications. 
       Springer, 2001. 
[3] J. Moon, Topics on tournaments. N. Y., 104 p., 1968. 
[4] M. Overbeck-Larish,   “A theorem on pancyclic oriented graphs”, J. Combin. Theory Ser. B 23, 
     168-173, 1977. 
[5] B. Jackson, “Long paths and cycles in oriented graphs”, J. Graph Theory, no. 5, pp.  145- 157, 1981. 
[6] Z. M. Song, “Pancyclic oriented graphs”, J. Graph Theory, no. 18, pp. 461-468, 1994.                      
      468, 1994. 
[7] J. Bang-Jensen  and  Y. Guo, “A note on vertex pancyclic oriented graphs”, Odense Universitet,  
[8] G. Gutin, “Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite 

digraphs”, Discrete Math, v. 141, pp. 153-162, 1995.   
[9] С. Х. Дарбинян,  “Îöåíêà äëèí êîíòóðîâ è ïóòåé â ðåãóëÿðíûõ íàïðàâëåííûõ 

ãðàôàõ”, Tanulmanyok , v. 135, pp. 131-144,  1982. 
[10] С. Х. Дарбинян,  К. М. Мосесян, “О панцикличности регулярных орграфов’,  ДАН Арм.  

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

ДАН Арм. ССР, т. LXXX,  № 4, ñòð. 51-54, 1985 ( ñì. òàêæå  Математические вопросы 
кибернетики и вычислительной техники,  № 14, ñòð. 55-74, 1985 ).  

[12] Ñ. Õ. Äàðáèíÿí,  È. À. Êàðàïåòÿí, “Î âåðøèííîé ïàíöèêëè÷íîñòè íàïðàâëåííûõ  
ãðàôîâ ñ áîëüøèìè ïîëóñòåïåíÿìè”, Математические вопросы кибернетики и 
вычислительной техники,  № 29, ñòð. 66-84, 2007. 

[13] Ñ. Õ. Äàðáèíÿí,  È. À. Êàðàïåòÿí, “Î êîíòóðàõ â íàïðàâëåííûõ    ãðàôàõ 
ïðîõîäÿùèõ ÷åðåç äàííóþ âåðøèíó”, Математические вопросы кибернетики и 
вычислительной техники,  № 31, ñòð.100--107, 2008. 

[14] S. Darbinyan  and  I. Karapetyan, “On vertex pancyclic oriented graphs, CSITConference, 
        pp.154-155, Yerevan, Armenia,  2005. 
      

                      



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

91 

 
àõÕÕ áñ¹í³Í ·ñ³ ýÝ»ñáõÙ ïñí³Í ·³·³Ãáí ³ÝóÝáÕ »ñϳñ  óÇÏÉ»ñÇ Ù³ëÇÝ 

 

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

²Ù÷á÷áõÙ 
 

Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ »Ã»  ( 12 n )- ·³·³Ã³ÝÇ )6( n     
áõÕÕáõñ¹í³Í G  ·ñ³ýÇ ó³Ýϳó³Í ·³·³ÃÇ ÉáÏ³É ÏÇë³³ëïÇ׳ÝÝ»ñÁ ÷áùñ ã»Ý  1n  
ÃíÇó, ³å³ G  ·ñ³ýÇ Ûáõñ³ù³ÝãÛáõñ ·³·³Ã ·ïÝíáõÙ ¿ n2    »ñϳñáõÃÛ³Ý ÏáÕÙÝáñáßí³Í 
óÇÏÉÇ íñ³: