problems for digraphs. However, to date there are very few results on this problem, even asymptotically. Let P 2, 2→ be the orientation of C 4 which consists of two 2-paths with the same initial and terminal vertices. Huang and Lyu [Discrete Math., 343 (5)(2020)] recently determined the Turán number of P 2, 2→, and considered it a more natural and interesting problem to determine the Turán number of directed cycles. Let P k→ and C k→ denote the …
Abstract
Brown et al. (J Combin Theory Ser B 15(1):77–93, 1973) considered Turán-type extremal problems for digraphs. However, to date there are very few results on this problem, even asymptotically. Let be the orientation of which consists of two 2-paths with the same initial and terminal vertices. Huang and Lyu [Discrete Math., 343 (5) (2020)] recently determined the Turán number of , and considered it a more natural and interesting problem to determine the Turán number of directed cycles. Let and denote the directed path and the directed cycle of order k, respectively. In this paper we determine the maximum size of -free digraphs of order n for all , as well as the extremal digraphs attaining this maximum size. Similar result is obtained for where n is large. In addition, we generalize the result of Huang and Lyu by characterizing the extremal digraphs avoiding an arbitrary orientation of except . In particular, for oriented even cycles, we classify which oriented even cycles inherit the difficulty of their underlying graphs and which do not.