Strong connectivity and directed triangles in oriented graphs. Partial results on a particular case of the Caccetta-H\"aggkvist conjecture

arXiv1112.3477MaRDI QIDQ6229705FDOQ6229705

Authors: Nicolas Lichiardopol 

Publication date: 15 December 2011

Abstract: A particular case of Caccetta-H"{a}ggkvist conjecture, says that a digraph of order $n$ with minimum out-degree at least $1/3n$ contains a directed cycle of length at most 3. Recently, Kral, Hladky and Norine proved that a digraph of order $n$ with minimum out-degree at least $0.3465n$ contains a directed cycle of length at most 3 (which currently is the best result). A weaker particular case says that a digraph of order $n$ with minimum semi-degree at least $1/3n$ contains a directed triangle. In a recent paper, by using the result of Kral et al, the author proved that for $$, any digraph $D$ of order $n$ with minimum semi-degree at least $$ contains a directed cycle of length at most 3 (which currently is the best result). This means that for a given integer $dgeq1$, every digraph with minimum semi-degree $d$ and of order $md$ with $mleq2.91082$, contains a directed cycle of length at most 3. In particular, every oriented graph with minimum semi-degree $d$ and of order $md$ with $mleq2.91082$, contains a directed triangle. In this paper, by using the result of Kral et al, we prove that every oriented graph with minimum semi-degree $d$, of order $md$ with $2.91082<mleq3$ and of strong connectivity at most $0.679d$, contains a directed triangle. This will be implied by a more general and more precise result, valid not only for $2.91082<mleq3$ but also for larger values of $m$. As application, we improve two existing results. The first result (Authors Broersma and Li), concerns the number of the directed cycles of length 4 of a triangle free oriented graph of order $n$ and of minimum semi-degree at least $fracn3$. The second result (Authors Kelly, K"{u}hn and Osthus), concerns the diameter of a triangle free oriented graph of order $n$ and of minimum semi-degree at least $fracn5$.

This page was built for publication: Strong connectivity and directed triangles in oriented graphs. Partial results on a particular case of the Caccetta-H\"aggkvist conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6229705)