Back to Search
Start Over
The Turán number of directed paths and oriented cycles.
- Source :
-
Graphs & Combinatorics . May2023, Vol. 39 Issue 3, p1-24. 24p. - Publication Year :
- 2023
-
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 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 directed path and the directed cycle of order k, respectively. In this paper we determine the maximum size of C k → -free digraphs of order n for all n , k ∈ N ∗ , as well as the extremal digraphs attaining this maximum size. Similar result is obtained for P k → where n is large. In addition, we generalize the result of Huang and Lyu by characterizing the extremal digraphs avoiding an arbitrary orientation of C 4 except P 2 , 2 → . In particular, for oriented even cycles, we classify which oriented even cycles inherit the difficulty of their underlying graphs and which do not. [ABSTRACT FROM AUTHOR]
- Subjects :
- *DIRECTED graphs
*EXTREMAL problems (Mathematics)
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 09110119
- Volume :
- 39
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Graphs & Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 163938249
- Full Text :
- https://doi.org/10.1007/s00373-023-02647-7