The Turán number of directed paths and oriented cycles

W Zhou, B Li - Graphs and Combinatorics, 2023 - Springer
W Zhou, B Li
Graphs and Combinatorics, 2023Springer
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 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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果