Microsoft Word - Gayane.doc Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè 31, 100--107, 2008. 100 Î êîíòóðàõ â íàïðàâëåííûõ ãðàôàõ ïðîõîäÿùèõ ÷åðåç äàííó þ âåðøèíó Ñàìâåë Õ. Äàðáèíÿí è Èñêàíäàð À. Êàðàïåòÿí Институт проблем информатики и автоматизации НАН РА samdarbin@ipia.sci.am, isko@ipia.sci.am Аннотация Ïóñòü G åñòü )12( n -âåðøèííûé ( n ≥6) íàïðàâëåííûé ãðàô ñ ìèíèìàëüíûìè ïîëуñòåïеíÿìè, íå ìеíüøèìè 1n . Äîêàçûâàåòñÿ, ÷òî ÷åðåç ëþáую âåðøèíу òàêîãî ãðàôà ïðîõîäèò êîíòóð äëèíû .12 n Литература [1] Ф. Харари, Теория графов, Мир, Москва, 1973. [2] J. Bang-Jensen and G. Gutin, Digraphs. Theory. Algorithms and Applications. Springer, 2001. [3] B. Jackson, “Long paths and cycles in oriented graphs”, J. Graph Theory, no. 5, pp. 145- 157 ,1981. [4] Z. M. Song, “Pancyclic oriented graphs”, J. Graph Theory, no. 18, pp. 461- 468 , 1994. [5] J. Bang-Jensen and Y. Guo, “A note on vertex pancyclic oriented graphs”, Odense Universitet, Preprint 20 , 1997. [6] G. Gutin, “Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs”, Discrete Math, v. 141, pp. 153-162, 1995. [7] С. Х. Дарбинян, “Îöåíêà äëèí êîíòóðîâ è ïóòåé â ðåãóëÿðíûõ íàïðàâëåííûõ ãðàôàõ”, Tanulmanyok , v. 135 , pp. 131-144, 1982. [8] С. Х. Дарбинян, К. М. Мосесян, “О панцикличности регулярных орграфов“, ДАН Арм. ССР, 1978, т. LXVII, № 4, ñòð. 208-211, 1978. [9] С. Х. Дарбинян, “О панцикличности направленных графов с большими полустепенями”, ДАН Арм. ССР, т. LXXX, № 4, ñòð. 51-54, 1985 (ñì. òàêæå Математические вопросы кибернетики и вычислительной техники, № 14, ñòð. 55-74, 1985). [10] Ñ. Õ. Äàðáèíÿí, È. À. Êàðàïåòÿí, “Î âåðøèííîé ïàíöèêëè÷íîñòè íàïðàâëåííûõ ãðàôîâ ñ áîëüøèìè ïîëóñòåïåíÿìè”, Математические вопросы кибернетики и вычислительной техники, № 29, ñòð. 66-84, 2007. [11] S. Darbinyan and I. Karapetyan, “On vertex pancyclic oriented graphs, CSIT Conference, pp.154-155, Yerevan, Armenia, 2005. Ñ. Äàðáèíÿí è È. Êàðàïåòÿí 101 àõÕÕ áñ¹í³Í ·ñ³ ýÝ»ñáõÙ ïñí³Í ·³·³Ãáí ³ÝóÝáÕ óÇÏÉ»ñÇ Ù³ëÇÝ ê. ¸³ñµÇÝÛ³Ý ¨ Æ. γñ³å»ïÛ³Ý ²Ù÷á÷áõÙ Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ »Ã» 12 n -·³·³Ã³ÝÇ )6( n áõÕÕáõñ¹í³Í G ·ñ³ýÇ ó³Ýϳó³Í ·³·³ÃÇ ÉáÏ³É ÏÇë³³ëïÇ׳ÝÝ»ñÁ ÷áùñ ã»Ý 1n ÃíÇó, ³å³ G ·ñ³ýÇ Ûáõñ³ù³ÝãÛáõñ ·³·³Ã ·ïÝíáõÙ ¿ 12 n »ñϳñáõÃÛ³Ý ÏáÕÙÝáñáßí³Í óÇÏÉÇ íñ³: