Research ArticleOpen AccessGoogle Scholar indexed
A Note on Directed 5-Cycles in Digraphs
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
- 1 Department of Mathematics Southwestern University of Finance and Economics Chengdu 611130, China
- 2 School of Mathematical Sciences University of Science and Technology of China Wentsun Wu Key Laboratory of CASHefei 230026, China
Copy link · social · email
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.
KeywordsDigraphDirected Cycle
- 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.
- 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.
- 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
- 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
- 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
- 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
- J. Shen, “Directed Triangles in Digraphs,” Journal of Combinatorial Theory, Series B, Vol. 74, 1998, pp. 405407.
- P. Hamburger, P. Haxell and A. Kostochka, “On the Directed Triangles in Digraphs,” Electronic Journal of Combinatorics, Vol. 14, No. 19, 2007.
- 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
- 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
- Q. Li and R. A. Brualdi, “On Minimal Regular Digraphs with Girth 4,” Czechoslovak Mathematical Journal, Vol. 33, 1983, pp. 439-447.
- J.-M. Xu, “Theory and Application of Graphs,” Kluwer Academic Publishers, Dordrecht/Boston/London, 2003.after