The Turan problems of directed paths and cycles in digraphs
Autor: | Zhou, Wenling, Li, Binlong |
---|---|
Rok vydání: | 2021 |
Předmět: | |
Druh dokumentu: | Working Paper |
Popis: | Let $\overrightarrow{P_k}$ and $\overrightarrow{C_k}$ denote the directed path and the directed cycle of order $k$, respectively. In this paper, we determine the precise maximum size of $\overrightarrow{P_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 $\overrightarrow{C_k}$-free digraphs of order $n$ as well as the extremal digraphs attaining the maximum size. In addition, Huang and Lyu [\textit{Discrete Math. 343(5) 2020}] characterized the extremal digraphs avoiding an orientation of $C_4$. For all other orientations of $C_4$, we also study the maximum size and the extremal digraphs avoiding them. Comment: 20 pages, 10 figures |
Databáze: | arXiv |
Externí odkaz: |