1. Introduction
Let
be a digragh without loops or parallel edges, where
is the vertex-set and
is the arc-set. In 1978, Caccetta and Häggkvist [1] made the following conjecture:
Conjecture 1.1 Any digraph on n vertices with minimum outdegree at least r contains a directed cycle of length at most
.
Trivially, this conjecture is true for
, and it has been proved for
by Caccetta and Häggkvist [1],
by Hamildoune [2],
and
by Hoáng and Reed [3],
by Shen [4]. While the general conjecture is still open, some weaker statements have been obtained. A summary of results and problems related to the Caccetta-Häggkvist conjecture sees Sullivan [5].
For the conjecture, the case
is trivial, the case
has received much attention, but this special case is still open. To prove the conjecture, one may seek as small a constant
as possible such that any digraph on n vertices with minimum outdegree at least
contains a directed triangle. The conjecture is that
. Caccetta and Häggkvist [1] obtained
, Bondy [6] showed
, Shen [7] gave
, Hamburger, Haxell, and Kostochka [8] improved it to 0.35312. Hladký, Král’ and Norin [9] further improved this bound to 0.3465. Namely, any digraph on n vertices with minimum out-degree at least 0.3465n contains a directed triangle. Very recently, Lichiardopol [10] showed that for
, any digraph on n vertices with both minimum out-degree and minimum in-degree at least
contains a cycle of length at most 3.
In this note, we consider the minimum constant
such that any digraph on n vertices with minimum outdegree at least
contains a directed cycle of length at most 5. The conjecture is that
. By refining the combinatorial techniques in [6,7,11], we prove the following result.
Theorem 1.2 If
, then any digraph on n vertices with minimum outdegree at least
contains a directed cycle of length at most 5.
2. Proof of Theorem 1.2
We prove Theorem 1.2 by induction on n. The theorem holds for
clearly. Now assume that the theorem holds for all digraphs with fewer than n vertices for
. Let G be a digraph on n vertices with minimum outdegree at least
. Suppose G contains no directed cycles with length at most 5. We can, without loss of generality, suppose that G is r-outregular, where
, that is, every vertex is of the outdegree r in G. We will try to deduce a contradiction. First we present some notations following [7].
For any
, let
and
, the outdegree of
;
and
, the indegree of
.
We say
a transitive triangle if
. The arc
is called the base of the transitive triangle.
For any
, let
and
, the number of induced 2-path with the first arc
;
and
, the number of induced 2-path with the last arc
;
and
, the number of transitive triangles with base
.
Lemma 2.1 For any
,
(1)
Proof: To prove this inequality, we consider two cases according to
or
.
If
, then substituting it into (1) yields
(2)
There exists some
with outdegree less than
in the subdigraph of G induced by
(Otherwise, this subdigraph would contain a directed 4-cycle by the induction hypothesis). Thus
.
Consider the subdigraph of G induced by
, by the induction hypothesis, some vertex
has outdegree less than
in this subdigraph. Thus, the set of outneighbors of x not in
satisfies
![](https://www.scirp.org/html/20-7400854\aa3e0c2e-e5d0-4689-b765-9efec91bb3a7.jpg)
Since
has no directed 5-cycle, then
,
,
,
and
are pairwise-disjoint sets with cardinalities r,
,
,
and
, we have that
![](https://www.scirp.org/html/20-7400854\00f06691-06a2-4f68-bcaf-0985e7f2d7a2.jpg)
Thus, the inequality (1) holds for
.
We now assume
. By the induction hypothesis, there is some vertex
that has outdegree less than
in the subdigraph of G induced by
, otherwise, this subdigraph would contain a directed 5-cycle. Also, w has not more than
outneighbors in the subdigraph of G induced by
. Let
be the outneighbors of w which is not in
. Noting that
, we have that
(3)
Because G has no directed triangle, all outneighbors of w are neither in
nor in
. Consider the subdigraph of G induced by
, by the induction hypothesis, there is some vertex
that has outdegree less than
in this subdigraph. Thus, the set of outneighbors of x not in
satisfies
(4)
Since G has no directed 4-cycle, all outneighbors of w are neither in
nor in
. Consider the subdigraph of G induced by
by the induction hypothesis, there is some vertex
![](https://www.scirp.org/html/20-7400854\46aff373-1374-4eba-9a0b-503f60096c4e.jpg)
that has outdegree less than
![](https://www.scirp.org/html/20-7400854\aec50ede-9c37-4086-8bf3-d39f3f26f6d7.jpg)
in this subdigraph. Thus, the set of outneighbors of y not in
satisfies
(5)
Because G has no directed cycle of length at most 5, then
,
,
,
,
and
are pairwise-disjoint sets of cardinalities r,
,
,
,
and
, we have that
![](https://www.scirp.org/html/20-7400854\829a144d-dba6-47cf-a4bc-844da7933bb2.jpg)
Substituting (3), (4) and (5) into this inequalities yields
![](https://www.scirp.org/html/20-7400854\d8a749e4-121f-46a1-a386-0d9ec9b2ef3e.jpg)
as desired, and so the lemma follows.
Connect to Proof of Theorem 1.2
Recalling that
, we can rewrite the inequality (1) as
(6)
Summing over all
, we have that
(7)
where t is the number of transitive triangles in G, and
(8)
By Cauchy’s inequality and the first theorem on graph theory (see, for example, Theorem 1.1 in [12]), we have that
![](https://www.scirp.org/html/20-7400854\a563a556-7a6a-4b64-a026-08a1e9481196.jpg)
that is
(9)
Because
and
are both equal to the number of induced directed 2-paths in G, it follows that
(10)
Summing over all
for the inequality (6) and substituting inequalities (7)-(10) into that inequality yields,
(11)
Noting that
(see Shen [7]), we have that
(12)
Combining (11) with (12) yields
(13)
Dividing both sides of the inequality (13) by
and noting that
, we get
![](https://www.scirp.org/html/20-7400854\e85e990d-edd0-4178-a72b-aa1b7875f3ab.jpg)
that is
![](https://www.scirp.org/html/20-7400854\be0d80eb-4b2b-4e78-bd4d-e7206909a637.jpg)
We obtain that
, a contradiction. This completes the proof of the theorem.
NOTES
#Corresponding author.