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

author:

Chen, Bin (Chen, Bin.) [1] | Chang, An (Chang, An.) [2] (Scholars:常安)

Indexed by:

Scopus SCIE

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 ((n-r+2)(2)) + r - 2 and the upper bound is tight, for r >= 2. Namely, they determined the Turan number of C-r-free strong digraphs of order n, where C-r = {C-2, C-3, ..., C-r} and C-i is a directed cycle of length i is an element of {2, 3, ..., r}. Specially, for r = 3, the maximum size of 3-free strong digraphs of order n is ((n-1)(2)) + 1. Let Phi(n)(xi, gamma) be a family of 3-free strong digraphs of order n in which the minimum out-degree is at least xi and the minimum in-degree is at least gamma, where both xi and gamma are positive integers. Let phi(n)(xi, gamma) be the maximum size of digraphs of Phi(n)(xi, gamma), i.e., Turan number of 3-free strong digraphs of order n with out and in-degree restrictions. We denote phi(n)(xi, gamma) = {D is an element of Phi(n)(xi, gamma) : the size of D is equal to phi(n)(xi, gamma)}. Recently, Chen et al. described phi(n)(1, 1), i.e., all 3-free strong digraphs of order n with size ((n-1)(2)) + 1. They also gave the bound of phi(n)(2, 1), that is, ((n-1)(2))-2 <= phi(n)(2, 1) <= ((n-1)(2)). In this paper, we improve the upper bound of phi(n)(2, 1) to ((n-1)(2)) - 1 and we thus get ((n-1)(2)) - 2 <= phi(n)(2, 1) <= ((n-1)(2)) - 1. In addition, we show that phi(n)(2, 1) = ((n-1)(2)) - 1 by constructing two 3-free strong digraphs with minimum out-degree two whose size reaches ((n-1)(2)) - 1 for n = 7, 8, and verify phi(n)(2, 1) = ((n-1)(2)) - 2 for n = 9. As a consequence, Turan number of 3-free strong digraphs of order n with out-degree at least two, i.e., phi(n)(2, 1), is one of ((n-1)(2)) - 1 and ((n-1)(2)) - 2. (C) 2022 Elsevier B.V. All rights reserved.

Keyword:

3-free strong digraph Out-degree Turan number

Community:

  • [ 1 ] [Chen, Bin]Fuzhou Univ, Ctr Discrete Math, Fuzhou, Fujian, Peoples R China
  • [ 2 ] [Chang, An]Fuzhou Univ, Ctr Discrete Math, Fuzhou, Fujian, Peoples R China

Reprint 's Address:

Show more details

Version:

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 Discipline: ENGINEERING;

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

Online/Total:54/10119609
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