| Title:
|
On short cycles in triangle-free oriented graphs (English) |
| Author:
|
Ji, Yurong |
| Author:
|
Wu, Shufei |
| Author:
|
Song, Hui |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
68 |
| Issue:
|
1 |
| Year:
|
2018 |
| Pages:
|
67-75 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
oriented graph |
| Keyword:
|
cycle |
| Keyword:
|
minimum semidegree |
| MSC:
|
05C20 |
| MSC:
|
05C38 |
| idZBL:
|
Zbl 06861567 |
| idMR:
|
MR3783585 |
| DOI:
|
10.21136/CMJ.2017.0131-16 |
| . |
| Date available:
|
2018-03-19T10:25:09Z |
| Last updated:
|
2020-07-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147121 |
| . |
| Reference:
|
[1] Bang-Jensen, J., Gutin, G. Z.: Digraphs: Theory, Algorithms and Applications.Springer Monographs in Mathematics, Springer, London (2001). Zbl 0958.05002, MR 1798170, 10.1007/978-1-84800-998-1 |
| Reference:
|
[2] Bondy, J. A.: Counting subgraphs a new approach to the Caccetta-Häggkvist conjecture.Discrete Math. 165-166 (1997), 71-80. Zbl 0872.05016, MR 1439261, 10.1016/S0012-365X(96)00162-8 |
| Reference:
|
[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. Zbl 0406.05033, MR 0527946 |
| Reference:
|
[4] Christofides, D., Keevash, P., Kühn, D., Osthus, D.: A semiexact degree condition for Hamilton cycles in digraphs.SIAM J. Discrete Math. 24 (2010), 709-756. Zbl 1223.05162, MR 2680211, 10.1137/090761756 |
| Reference:
|
[5] Hamburger, P., Haxell, P., Kostochka, A.: On directed triangles in digraphs.Electron. J. Comb. 14 (2007), Research Paper N19, 9 pages. Zbl 1157.05311, MR 2350447 |
| Reference:
|
[6] Hladký, J., Kráľ, D., Norin, S.: Counting flags in triangle-free digraphs.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. Zbl 1273.05107, MR 2720903, 10.1016/j.endm.2009.07.105 |
| Reference:
|
[7] Keevash, P., Kühn, D., Osthus, D.: An exact minimum degree condition for Hamilton cycles in oriented graphs.J. Lond. Math. Soc., II. Ser. 79 (2009), 144-166. Zbl 1198.05081, MR 2472138, 10.1112/jlms/jdn065 |
| Reference:
|
[8] Kelly, L., Kühn, D., Osthus, D.: A Dirac-type result on Hamilton cycles in oriented graphs.Comb. Probab. Comput. 17 (2008), 689-709. Zbl 1172.05038, MR 2454564, 10.1017/S0963548308009218 |
| Reference:
|
[9] Kelly, L., Kühn, D., Osthus, D.: Cycles of given length in oriented graphs.J. Comb. Theory, Ser. B 100 (2010), 251-264. Zbl 1274.05257, MR 2595670, 10.1016/j.jctb.2009.08.002 |
| Reference:
|
[10] Kühn, D., Osthus, D.: A survey on Hamilton cycles in directed graphs.Eur. J. Comb. 33 (2012), 750-766. Zbl 1239.05114, MR 2889513, 10.1016/j.ejc.2011.09.030 |
| Reference:
|
[11] Kühn, D., Osthus, D., Treglown, A.: Hamiltonian degree sequences in digraphs.J. Comb. Theory, Ser. B 100 (2010), 367-380. Zbl 1209.05138, MR 2644240, 10.1016/j.jctb.2009.11.004 |
| Reference:
|
[12] Lichiardopol, N.: A new bound for a particular case of the Caccetta-Häggkvist conjecture.Discrete Math. 310 (2010), 3368-3372. Zbl 1222.05087, MR 2721097, 10.1016/j.disc.2010.07.026 |
| Reference:
|
[13] Razborov, A. A.: Flag algebras.J. Symb. Log. 72 (2007), 1239-1282. Zbl 1146.03013, MR 2371204, 10.2178/jsl/1203350785 |
| Reference:
|
[14] Shen, J.: Directed triangles in digraphs.J. Comb. Theory, Ser. B 74 (1998), 405-407. Zbl 0904.05035, MR 1654164, 10.1006/jctb.1998.1839 |
| Reference:
|
[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). |
| . |
