О контурах в направленных графах проходящих через данную вершину
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
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
