The Turan problems of directed paths and cycles in digraphs

2021/02/21 by Zhou, Wenling, Li, Binlong
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2102.10529

Abstract

Let \overrightarrowP_k and \overrightarrowC_k denote the directed path and the directed cycle of order k, respectively. In this paper, we determine the precise maximum size of \overrightarrowP_k-free digraphs of order n as well as the extremal digraphs attaining the maximum size for large n. For all n, we also determine the precise maximum size of \overrightarrowC_k-free digraphs of order n as well as the extremal digraphs attaining the maximum size. In addition, Huang and Lyu [Discrete Math. 343(5) 2020] characterized the extremal digraphs avoiding an orientation of C₄. For all other orientations of C₄, we also study the maximum size and the extremal digraphs avoiding them.

Related

• Turán problems for digraphs avoiding distinct walks of a given length with the same endpoints
• Generalized Turán problem for directed cycles
• Turan problems for k-geodetic digraphs
• Extremal digraphs avoiding an orientation of C₄
• Extremal digraphs containing at most t paths of length 2 with the same endpoints