• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Chen, B. (Chen, B..) [1] | Chang, A. (Chang, A..) [2]

Indexed by:

Scopus

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:

3-free strong digraph; Out-degree; Turán number

Community:

  • [ 1 ] [Chen, B.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian, China
  • [ 2 ] [Chang, A.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian, China

Reprint 's Address:

  • [Chen, B.]Center for Discrete Mathematics, Fuzhou, China

Show more details

Related Keywords:

Related Article:

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:

WoS CC 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:

Online/Total:1534/10128989
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1