Geodesic
On short cycles in triangle-free oriented graphs
Czechoslovak Mathematical Journal, Tome 68 (2018) no. 1, pp. 67-75

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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$.
DOI : 10.21136/CMJ.2017.0131-16
Classification : 05C20, 05C38
Keywords: oriented graph; cycle; minimum semidegree 
@article{10_21136_CMJ_2017_0131_16,
     author = {Ji, Yurong and Wu, Shufei and Song, Hui},
     title = {On short cycles in triangle-free oriented graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {67--75},
     publisher = {mathdoc},
     volume = {68},
     number = {1},
     year = {2018},
     doi = {10.21136/CMJ.2017.0131-16},
     mrnumber = {3783585},
     zbl = {06861567},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0131-16/}
}
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
SP  - 67
EP  - 75
VL  - 68
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0131-16/
DO  - 10.21136/CMJ.2017.0131-16
LA  - en
ID  - 10_21136_CMJ_2017_0131_16
ER  - 
%0 Journal Article
%A Ji, Yurong
%A Wu, Shufei
%A Song, Hui
%T On short cycles in triangle-free oriented graphs
%J Czechoslovak Mathematical Journal
%D 2018
%P 67-75
%V 68
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0131-16/
%R 10.21136/CMJ.2017.0131-16
%G en
%F 10_21136_CMJ_2017_0131_16
Ji, Yurong; Wu, Shufei; Song, Hui. On short cycles in triangle-free oriented graphs. Czechoslovak Mathematical Journal, Tome 68 (2018) no. 1, pp. 67-75. doi: 10.21136/CMJ.2017.0131-16

Cité par Sources :