A Note on Directed 5-Cycles in Digraphs

Hao Liang, Junming Xu

Department of Mathematics Southwestern University of Finance and Economics Chengdu 611130, China.
School of Mathematical Sciences University of Science and Technology of China Wentsun Wu Key Laboratory of CASHefei 230026, China.

DOI: 10.4236/am.2012.37120                

Abstract

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

Keywords

Digraph; Directed Cycle

Conflicts of Interest

The authors declare no conflicts of interest.

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. 405407.
[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. Hladky, 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.after