﻿A Note on Directed 5-Cycles in Digraphs

Applied Mathematics
Vol. 3  No. 7 (2012) , Article ID: 20013 , 4 pages DOI:10.4236/am.2012.37120

A Note on Directed 5-Cycles in Digraphs*

Hao Liang1#, Junming Xu2

1Department of Mathematics, Southwestern University of Finance and Economics, Chengdu, China

2School of Mathematical Sciences, University of Science and Technology of China, Wentsun Wu Key Laboratory of CAS, Hefei, China

Email: #lianghao@mail.ustc.edu.cn

Received May 18, 2012; revised June 18, 2012; accepted June 25, 2012

Keywords: Digraph; Directed Cycle

ABSTRACT

In this note, it is proved that if, then any digraph on n vertices with minimum outdegree at least contains a directed cycle of length at most 5.

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

Since has no directed 5-cycle, then, , , and are pairwise-disjoint sets with cardinalities r, ,

, and, we have that

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

that has outdegree less than

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

Substituting (3), (4) and (5) into this inequalities yields

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

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) byand noting that, we get

that is

We obtain that, a contradiction. This completes the proof of the theorem.

REFERENCES

1. L. Caccetta and R. Häggkvist, “On Minimal Digraphs with Given Girth,” Proceedings of the 9th Southeast Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, 1978, pp. 181-187.
2. Y. O. Hamidoune, “A Note on Minimal Directed Graphs with Given Girth,” Journal of Combinatorial Theory, Series B, Vol. 43, No. 3, 1987, pp. 343-348.
3. C. Hoáng and B. Reed, “A Note on Short Cycles in Digraphs,” Discrete Mathematics, Vol. 66, No. 1-2, 1987, pp. 103-107. doi:10.1016/0012-365X(87)90122-1
4. J. Shen, “On the Girth of Digraphs,” Discrete Mathematics, Vol. 211, No. 1-3, 2000, pp. 167-181. doi:10.1016/S0012-365X(99)00323-4
5. B. D. Sullivan, “A Summary of Results and Problems Related to the Caccetta-Häggkvist Conjecture,” 2006. http://www.aimath.org/WWN/caccetta/caccetta.pdf
6. J. A. Bondy, “Counting Subgraphs: A New Approach to the Caccetta-Häggkvist Conjecture,” Discrete Mathematics, Vol. 165-166, 1997, pp. 71-80. doi:10.1016/S0012-365X(96)00162-8
7. J. Shen, “Directed Triangles in Digraphs,” Journal of Combinatorial Theory, Series B, Vol. 74, 1998, pp. 405- 407.
8. P. Hamburger, P. Haxell and A. Kostochka, “On the Directed Triangles in Digraphs,” Electronic Journal of Combinatorics, Vol. 14, No. 19, 2007.
9. J. Hladký, D. Král’ and S. Norin, “Counting Flags in Triangle-Free Digraphs,” Electronic Notes in Discrete Mathematics, Vol. 34, 2009, pp. 621-625. doi:10.1016/j.endm.2009.07.105
10. N. Lichiardopol, “A New Bound for a Particular Case of the Caccetta-Häggkvist Conjecture,” Discrete Mathematics, Vol. 310, No. 23, 2010, pp. 3368-3372. doi:10.1016/j.disc.2010.07.026
11. Q. Li and R. A. Brualdi, “On Minimal Regular Digraphs with Girth 4,” Czechoslovak Mathematical Journal, Vol. 33, 1983, pp. 439-447.
12. J.-M. Xu, “Theory and Application of Graphs,” Kluwer Academic Publishers, Dordrecht/Boston/London, 2003.

NOTES

*Supported by NNSF of China (No. 11071233).

#Corresponding author.