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

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 – 1.

References

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

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

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.

J. Bang-Jensen and Y. Guo, “A note on vertex pancyclic oriented graphs”, Odense Universitet, Preprint 20, 1997.

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.

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, 100–107. Retrieved from https://mpcs.sci.am/index.php/mpcs/article/view/396