Share This Article:

A Note on Directed 5-Cycles in Digraphs

Abstract Full-Text HTML XML Download Download as PDF (Size:77KB) PP. 805-808
DOI: 10.4236/am.2012.37120    3,328 Downloads   5,295 Views   Citations

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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

  
comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.