Generalized Turán problem for directed cycles
Preprint
Abstract
For integers $k, \ell \geq 3$, let $\mathrm{ex}(n, \overrightarrow{C_k}, \overrightarrow{C_\ell})$ denote the maximum number of directed cycles of length $k$ in any oriented graph on $n$ vertices which does not contain a directed cycle of length $\ell$. We establish the order of magnitude of $\mathrm{ex}(n, \overrightarrow{C_k}, \overrightarrow{C_\ell})$ for every $k$ and $\ell$ and determine its value up to a lower error term when $k \nmid \ell$ and $\ell$ is large enough. Additionally, we calculate the value of $\mathrm{ex}(n, \overrightarrow{C_k}, \overrightarrow{C_\ell})$ for some other specific pairs $(k, \ell)$ showing that a diverse class of extremal constructions can appear for small values of $\ell$.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Cycles of a given length in tournamentsJournal of Combinatorial Theory, Series B, 2022
- On the maximum number of odd cycles in graphs without smaller odd cyclesJournal of Graph Theory, 2021
- Many T copies in H-free graphsJournal of Combinatorial Theory, Series B, 2016
- On the number of pentagons in triangle-free graphsJournal of Combinatorial Theory, Series A, 2013
- On the maximum number of five-cycles in a triangle-free graphJournal of Combinatorial Theory, Series B, 2012
- On the connection between chromatic number, maximal clique and minimal degree of a graphDiscrete Mathematics, 1974
- On Subvariants, i.e. Semi-Invariants to Binary Quantics of an Unlimited OrderAmerican Journal of Mathematics, 1882