A Note on Directed 5-Cycles in Digraphs

Affiliation(s)

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.

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.

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.

In this note, it is proved that if

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.

H. Liang and J. Xu, "A Note on Directed 5-Cycles in Digraphs,"

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

[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