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 ((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:
Reprint 's Address:
Email:
Version:
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:
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: