On short cycles in triangle-free oriented graphs

Yurong Ji; Shufei Wu; Hui Song

Czechoslovak Mathematical Journal (2018)

  • Volume: 68, Issue: 1, page 67-75
  • ISSN: 0011-4642

Abstract

top
An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on n vertices with minimum outdegree d contains a directed cycle of length at most ⌈ n / d ⌉ . In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that α 0 is the smallest real such that every n -vertex digraph with minimum outdegree at least α 0 n contains a directed triangle. Let ϵ < ( 3 - 2 α 0 ) / ( 4 - 2 α 0 ) be a positive real. We show that if D is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least ( 1 / ( 4 - 2 α 0 ) + ϵ ) | D | , then each vertex of D is contained in a directed cycle of length l for each 4 ≤ l < ( 4 - 2 α 0 ) ϵ | D | / ( 3 - 2 α 0 ) + 2 .

How to cite

top

Ji, Yurong, Wu, Shufei, and Song, Hui. "On short cycles in triangle-free oriented graphs." Czechoslovak Mathematical Journal 68.1 (2018): 67-75. <http://eudml.org/doc/294426>.

@article{Ji2018,
abstract = {An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $\lceil n / d\rceil $. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $\alpha _0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least $\alpha _0n$ contains a directed triangle. Let $\epsilon < \{(3-2\alpha _0)\}/\{(4-2\alpha _0)\}$ be a positive real. We show that if $D$ is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least $(1/\{(4-2\alpha _0)\}+\epsilon )|D|$, then each vertex of $D$ is contained in a directed cycle of length $l$ for each $4\le l< \{(4-2\alpha _0)\epsilon |D|\}/\{(3-2\alpha _0)\}+2$.},
author = {Ji, Yurong, Wu, Shufei, Song, Hui},
journal = {Czechoslovak Mathematical Journal},
keywords = {oriented graph; cycle; minimum semidegree},
language = {eng},
number = {1},
pages = {67-75},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On short cycles in triangle-free oriented graphs},
url = {http://eudml.org/doc/294426},
volume = {68},
year = {2018},
}

TY - JOUR
AU - Ji, Yurong
AU - Wu, Shufei
AU - Song, Hui
TI - On short cycles in triangle-free oriented graphs
JO - Czechoslovak Mathematical Journal
PY - 2018
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 68
IS - 1
SP - 67
EP - 75
AB - An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $\lceil n / d\rceil $. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $\alpha _0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least $\alpha _0n$ contains a directed triangle. Let $\epsilon < {(3-2\alpha _0)}/{(4-2\alpha _0)}$ be a positive real. We show that if $D$ is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least $(1/{(4-2\alpha _0)}+\epsilon )|D|$, then each vertex of $D$ is contained in a directed cycle of length $l$ for each $4\le l< {(4-2\alpha _0)\epsilon |D|}/{(3-2\alpha _0)}+2$.
LA - eng
KW - oriented graph; cycle; minimum semidegree
UR - http://eudml.org/doc/294426
ER -

References

top
  1. Bang-Jensen, J., Gutin, G. Z., 10.1007/978-1-84800-998-1, Springer Monographs in Mathematics, Springer, London (2001). (2001) Zbl0958.05002MR1798170DOI10.1007/978-1-84800-998-1
  2. Bondy, J. A., 10.1016/S0012-365X(96)00162-8, Discrete Math. 165-166 (1997), 71-80. (1997) Zbl0872.05016MR1439261DOI10.1016/S0012-365X(96)00162-8
  3. Caccetta, L., Häggkvist, R., On minimal digraphs with given girth, Proc. 9th Southeast. Conf. on Combinatorics, Graph Theory, and Computing: Florida Atlantic University. Boca Raton, 1978 Congress. Numer. 21, Utilitas Math. Publishing, Winnipeg (1978), 181-187. (1978) Zbl0406.05033MR0527946
  4. Christofides, D., Keevash, P., Kühn, D., Osthus, D., 10.1137/090761756, SIAM J. Discrete Math. 24 (2010), 709-756. (2010) Zbl1223.05162MR2680211DOI10.1137/090761756
  5. Hamburger, P., Haxell, P., Kostochka, A., On directed triangles in digraphs, Electron. J. Comb. 14 (2007), Research Paper N19, 9 pages. (2007) Zbl1157.05311MR2350447
  6. Hladký, J., Kráľ, D., Norin, S., 10.1016/j.endm.2009.07.105, Extended abstracts of the 5th European Conf. on Combinatorics, Graph Theory and Applications Bordeaux, 2009, Elsevier, Amsterdam, Electronic Notes in Discrete Mathematics 34 J. Nešetřil et al. (2009), 621-625. (2009) Zbl1273.05107MR2720903DOI10.1016/j.endm.2009.07.105
  7. Keevash, P., Kühn, D., Osthus, D., 10.1112/jlms/jdn065, J. Lond. Math. Soc., II. Ser. 79 (2009), 144-166. (2009) Zbl1198.05081MR2472138DOI10.1112/jlms/jdn065
  8. Kelly, L., Kühn, D., Osthus, D., 10.1017/S0963548308009218, Comb. Probab. Comput. 17 (2008), 689-709. (2008) Zbl1172.05038MR2454564DOI10.1017/S0963548308009218
  9. Kelly, L., Kühn, D., Osthus, D., 10.1016/j.jctb.2009.08.002, J. Comb. Theory, Ser. B 100 (2010), 251-264. (2010) Zbl1274.05257MR2595670DOI10.1016/j.jctb.2009.08.002
  10. Kühn, D., Osthus, D., 10.1016/j.ejc.2011.09.030, Eur. J. Comb. 33 (2012), 750-766. (2012) Zbl1239.05114MR2889513DOI10.1016/j.ejc.2011.09.030
  11. Kühn, D., Osthus, D., Treglown, A., 10.1016/j.jctb.2009.11.004, J. Comb. Theory, Ser. B 100 (2010), 367-380. (2010) Zbl1209.05138MR2644240DOI10.1016/j.jctb.2009.11.004
  12. Lichiardopol, N., 10.1016/j.disc.2010.07.026, Discrete Math. 310 (2010), 3368-3372. (2010) Zbl1222.05087MR2721097DOI10.1016/j.disc.2010.07.026
  13. Razborov, A. A., 10.2178/jsl/1203350785, J. Symb. Log. 72 (2007), 1239-1282. (2007) Zbl1146.03013MR2371204DOI10.2178/jsl/1203350785
  14. Shen, J., 10.1006/jctb.1998.1839, J. Comb. Theory, Ser. B 74 (1998), 405-407. (1998) Zbl0904.05035MR1654164DOI10.1006/jctb.1998.1839
  15. Sullivan, B. D., A summary of results and problems related to the Caccetta-Häggkvist conjecture, Available at ArXiv:math/0605646v1 [math.CO] (2006). (2006) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.