We consider vertex decompositions of (di)graphs appearing in the automata theory and establish some properties of these decompositions. These decompositions are applied to the problem of forbidden subgraphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Dokuchaev, B. Novikov, and G. Zholtkevych, “Partial actions and automata,” Alg. Discrete Math., 11, No. 2, 51–63 (2011).
A.V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling. Vol. 2. Compiling, Prentice-Hall (1973).
B. Bollobas, “Modern graph theory,” Grad. Texts Math., 184 (1998).
D. B. West, Introduction to Graph Theory, Pearson Education (2001).
P. Turán, “On an extremal problem in graph theory (in Hungarian),” Mat. Fiz. Lapok, 46, 436–452 (1941).
E. M. Eschen, Ch. T. Hoang, J. P. Spinrad, and R. Sritharan, “On graphs without a C 4 or a diamond,” Discrete Appl. Math., 159, No. 7, 581–587 (2011).
Author information
Authors and Affiliations
Additional information
Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 66, No. 7, pp. 958–969, July, 2014.
Rights and permissions
About this article
Cite this article
Novikov, B.V., Polyakova, L.Y. & Zholtkevich, G.N. Decomposition of Directed Graphs and the Turán Problem. Ukr Math J 66, 1070–1084 (2014). https://doi.org/10.1007/s11253-014-0995-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11253-014-0995-7