2011/12/15 by Nicolas Lichiardopol, Lichiardopol, Nicolas
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory #Optimization and Search Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1112.3477
14 pages
arxiv created 2011/12/15 · openalex publication_date 2011/12/15 · arxiv updated 2011/12/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
A particular case of Caccetta-Hä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 β≥ 0.343545, any digraph D of order n with minimum semi-degree at least βn contains a directed cycle of length at most 3 (which currently is the best result). This means that for a given integer d≥ 1, every digraph with minimum semi-degree d and of order md with m≤ 2.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 m≤ 2.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< m≤ 3 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< m≤ 3 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 (n)/(3). The second result (Authors Kelly, Kühn and Osthus), concerns the diameter of a triangle free oriented graph of order n and of minimum semi-degree at least (n)/(5).