On directed triangles in digraphs
type: Item
instance of: scholarly article
title: On directed triangles in digraphs
zbMATH Open document ID: 1157.05311
author: Peter Hamburger
author: Penny Haxell
author: Alexandr Kostochka
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129672
full work available at URL: v14i1n19.html
review text: Summary: Using a recent result of \textit{M. Chudnovsky}, \textit{P. Seymour}, and \textit{B. Sullivan} [''Cycles in dense digraphs'', Combinatorica 28, No.\,1, 1--18 (2008; Zbl 1174.05049)], we slightly improve two bounds related to the Caccetta-Häggkvist Conjecture [\textit{L. Caccetta} and \textit{R. Häggkvist}, ''On minimal digraphs with given girth'', Congressus Numerantium XXI, 181--187 (1978; Zbl 0406.05033) ]. Namely, we show that if \(\alpha\geq 0.35312\), then each \(n\)-vertex digraph \(D\) with minimum outdegree at least \(\alpha n\) has a directed 3-cycle. If \(\beta\geq 0.34564\), then every \(n\)-vertex digraph \(D\) in which the outdegree and the indegree of each vertex is at least \(\beta n\) has a directed 3-cycle.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5540819
zbMATH Keywords: digraph
zbMATH Keywords: minimum outdegree
zbMATH Keywords: derected cycle
zbMATH Keywords: indegree
zbMATH Keywords: outdegree
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540819