AM  Vol.3 No.7 , July 2012
A Note on Directed 5-Cycles in Digraphs
Author(s) Hao Liang*, Junming Xu
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.

Cite this paper
H. Liang and J. Xu, "A Note on Directed 5-Cycles in Digraphs," Applied Mathematics, Vol. 3 No. 7, 2012, pp. 805-808. doi: 10.4236/am.2012.37120.
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

 
 
Top