Indexed by:
Abstract:
A digraph D is r-free if such D has no directed cycles of length at most r, where r is a positive integer. In 1980, Bermond et al. showed that if D is an r-free strong digraph of order n, then the size of D is at most [Formula presented] and the upper bound is tight, for r≥2. Namely, they determined the Turán number of Cr-free strong digraphs of order n, where Cr={C2,C3,…,Cr} and Ci is a directed cycle of length i∈{2,3,…,r}. Specially, for r=3, the maximum size of 3-free strong digraphs of order n is [Formula presented]. Let Φn(ξ,γ) be a family of 3-free strong digraphs of order n in which the minimum out-degree is at least ξ and the minimum in-degree is at least γ, where both ξ and γ are positive integers. Let φn(ξ,γ) be the maximum size of digraphs of Φn(ξ,γ), i.e., Turán number of 3-free strong digraphs of order n with out and in-degree restrictions. We denote ϕn(ξ,γ)={D∈Φn(ξ,γ):thesizeofDisequaltoφn(ξ,γ)}. Recently, Chen et al. described ϕn(1,1), i.e., all 3-free strong digraphs of order n with size [Formula presented]. They also gave the bound of φn(2,1), that is, [Formula presented]. In this paper, we improve the upper bound of φn(2,1) to [Formula presented] and we thus get [Formula presented]. In addition, we show that [Formula presented] by constructing two 3-free strong digraphs with minimum out-degree two whose size reaches [Formula presented] for n=7,8, and verify [Formula presented] for n=9. As a consequence, Turán number of 3-free strong digraphs of order n with out-degree at least two, i.e., φn(2,1), is one of [Formula presented] and [Formula presented]. © 2022 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Applied Mathematics
ISSN: 0166-218X
Year: 2022
Volume: 314
Page: 252-264
1 . 1
JCR@2022
1 . 0 0 0
JCR@2023
ESI HC Threshold:66
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: