Article in press
Authors:
Title:
Turán number of strong digraphs forbidden at least two triangles
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-10-15 , Revised: 2025-06-05 , Accepted: 2025-06-10 , Available online: 2025-08-01 , https://doi.org/10.7151/dmgt.2595
Abstract:
Let $\mathcal{F}$ be a family of digraphs. A digraph $D$ is $\mathcal{F}$-free
if it has no isomorphic copy of any member of $\mathcal{F}$. The Turán number
$ex(n,\mathcal{F})$ is the largest number of arcs of $\mathcal{F}$-free digraphs
on $n$ vertices. Bermond, Germa, Heydemann and Sotteau in 1980 [Girth in
digraphs, J. Graph Theory, 4 (1980), 337–341] determined the Turán number
of $\mathcal{C}_{k}$-free strong digraphs on $n$ vertices for $k\geq2$, where
$\mathcal{C}_{k}=\{C_{2}, C_{3},\ldots,C_{k}\}$ and $C_{i}$ is a directed cycle
of length $i\in \{2,3,\ldots,k\}$. In this paper, we determine all Turán
number of strong digraphs without $t\geq2$ triangles, extending the previous
result for the case $k=3$.
Keywords:
Turán number, strong digraph, triangle
References:
- J.C. Bermond, A. Germa, M.C. Heydemann and D. Sotteau, Girth in digraphs, J. Graph Theory 4(3) (1980) 337–341.
https://doi.org/10.1002/jgt.3190040311 - W.G. Brown and F. Harary, Extremal digraphs, in: Combinatorial Theory and its Applications, Colloq. Math. Soc. J. Bolyai 4 (1970) 135–198.
- W.G. Brown, P. Erdős and M. Simonovits, Extremal problems for directed graphs, J. Combin. Theory Ser. B 15 (1973) 77–93.
https://doi.org/10.1016/0095-8956(73)90034-8 - W.G. Brown, P. Erdős and M. Simonovits, Algorithmic solution of extremal digraph problems, Trans. Amer. Math. Soc. 292 (1985) 421–449.
https://doi.org/10.1090/S0002-9947-1985-0808730-0 - W.G. Brown and M. Simonovits, Extremal multigraph and digraph problems, in: Paul Erdős and His Mathematics, II, G. Halasz, L. Lovasz, M. Simonovits and V.T. Sós (Ed(s)), Bolyai Soc. Math. Stud. 11, (Springer, Berlin, Heidelberg, 2002) 157–203.
- S. Cambie, Maximum size of digraphs of given radius, Discrete Math. 346 (2023) 113429.
https://doi.org/10.1016/j.disc.2023.113429 - B. Chen and A. Chang, $3$-free strong digraphs with the maximum size, Graphs Combin. 37 (2021) 2535–2554.
https://doi.org/10.1007/s00373-021-02373-y - B. Chen and A. Chang, Turán number of $3$-free strong digraphs with out-degree restriction, Discrete Appl. Math. 314 (2022) 252–264.
https://doi.org/10.1016/j.dam.2022.03.009 - B. Chen and X. Hou, Maximum size of $C_{\leq k}$-free strong digraphs with out-degree at least two (2022).
arXiv: 2211.03129v1 - M. Chudnovsky, P. Seymour and B. Sullivan, Cycles in dense digraphs, Combinatorica 28 (2008) 1–18.
https://doi.org/10.1007/s00493-008-2331-z - P. Dankelmann, Distance and size in digraphs, Discrete Math. 338 (2015) 144–148.
https://doi.org/10.1016/j.disc.2014.08.028 - Z. Huang, Z. Lyu and P. Qiao, A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints, Discrete Math. 342 (2019) 1703–1717.
https://doi.org/10.1016/j.disc.2019.02.002 - Z. Huang and X. Zhan, Digraphs that have at most one walk of a given length with the same endpoints, Discrete Math. 311 (2011) 70–79.
https://doi.org/10.1016/j.disc.2010.09.025 - Z. Lyu, Digraphs that contain at most $t$ distinct walks of a given length with the same endpoints, J. Comb. Optim. 41 (2021) 762–779.
https://doi.org/10.1007/s10878-021-00718-0 - Z. Lyu, Extremal digraphs avoiding an orientation of the diamond, Graphs Combin. 37 (2021) 1373–1383.
https://doi.org/10.1007/s00373-021-02324-7 - W. Mantel, Problem $28$, Wiskundige Opgaven 10 (1907) 60–61.
- J.W. Moon, On subtournaments of a tournament, Canad. Math. Bull. 9 (1966) 297–301.
https://doi.org/10.4153/CMB-1966-038-7 - P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.
- X. Zhan, Matrix Theory, Grad. Stud. Math. 147 (Amer. Math. Soc., Providence, Rhode Island, 2013).
https://doi.org/10.1090/gsm/147
Close