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