О длинных контурах в направленных графах, проходящих через данну ю вершину

Authors

  • Самвел Х. Дарбинян Institute for Informatics and Automation Problems of NAS RA
  • Искандар А. Карапетян Institute for Informatics and Automation Problems of NAS RA

Abstract

Пусть G есть (2n+1)-вершинный (n ≥ 6) направленный граф с минимальными полустепенями, не меньшими n–1. Доказывается, что через любую вершину такого графа проходит контур длины 2n.

References

Ф. Харари, Теория графов, Мир, Москва, 1973.

J. Bang-Jensen and G. Gutin, Digraphs. Theory. Algorithms and Applications.Springer, 2001.

J. Moon, Topics on tournaments. N. Y., 104 p., 1968.

M. Overbeck-Larish, “A theorem on pancyclic oriented graphs”, J. Combin. Theory Ser. B 23,168-173, 1977.

B. Jackson, “Long paths and cycles in oriented graphs”, J. Graph Theory, no. 5, pp. 145- 157, 1981.

Z. M. Song, “Pancyclic oriented graphs”, J. Graph Theory, no. 18, pp. 461-468, 1994.468, 1994.

J. Bang-Jensen and Y. Guo, “A note on vertex pancyclic oriented graphs”,Journal of Graph Theory, vol 31, pp. 313-318, 1999, Odense Universitet.

G. Gutin, “Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs”, Discrete Math, v. 141, pp. 153-162, 1995.

С. Х. Дарбинян, “Оценка длин контуров и путей в регулярных направленных графах”, Tanulmanyok , v. 135, pp. 131-144, 1982.

С. Х. Дарбинян, К. М. Мосесян, “О панцикличности регулярных орграфов’, ДАН Арм.ССР, 1978, т. LXVII, № 4, стр. 208-211, 1978.

С. Х. Дарбинян, “О панцикличности направленных графов с большими полустепенями”, ДАН Арм. ССР, т. LXXX, № 4, стр. 51-54, 1985.

С. Х. Дарбинян, И. А. Карапетян, “О вершинной панцикличности направленных графов с большими полустепенями”, Математические вопросы кибернетики и вычислительной техники, № 29, стр. 66-84, 2007.

С. Х. Дарбинян, И. А. Карапетян, “О контурах в направленных графахпроходящих через данную вершину”, Математические вопросы кибернетики ивычислительной техники, № 31, стр.100--107, 2008.

S. Darbinyan and I. Karapetyan, “On vertex pancyclic oriented graphs, CSIT Conference, pp.154-155, Yerevan, Armenia, 2005.

С. Х. Дарбинян, “О панцикличности направленных графов с большими полустепенями”, Математические вопросы кибернетики и вычислительной техники, № 14, стр. 55-74, 1985.

Downloads

Published

2008-09-25

How to Cite

Дарбинян, С. Х. ., & Карапетян, И. А. . (2008). О длинных контурах в направленных графах, проходящих через данну ю вершину. Mathematical Problems of Computer Science, 31, 90–99. Retrieved from https://mpcs.sci.am/index.php/mpcs/article/view/395