Destroying cycles in digraphs
type: Item
instance of: scholarly article
title: Destroying cycles in digraphs
zbMATH Open document ID: 1249.05163
author: Molly Dunkum
author: Peter Hamburger
author: Attila Pór
published in: Combinatorica
publication date: 2011-12-20T00:00:00Z
review text: Every 3-free tournament is acyclic. The present paper investigates the following question: If a simple 3-free digraph is obtained from a tournament by deleting \(k\) edges, what is the minimum number of additional edges that must be deleted in order to obtain an acyclic digraph? The result improves some earlier upper bounds by other researchers (\textit{M. Chudnovsky, P. Seymour} and \textit{B. Sullivan} [Combinatorica 28, 1--18 (2008; Zbl 1174.05049)], \textit{P. Hamburger, P. Haxell} and \textit{A. Kostochka} [Electron. J. Comb. 14, No. 1, Research Paper N19 (2007; Zbl 1157.05311)]) but does not prove the conjecture that each \(n\)-vertex digraph with minimum outdegree at least \(n/3\) contains a directed triangle (\textit{L. Caccetta} and \textit{R. Häggkvist} [Congressus Numerantium XXI, 181--187 (1978; Zbl 0406.05033)]).
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5990942
zbMATH Keywords: cycles
zbMATH Keywords: digraphs
zbMATH Keywords: acyclic, 3-free digraph
MaRDI profile type: Publication
full work available at URL: s00493-011-2589-4
OpenAlex ID: W2078309664
cites work: Cycles in dense digraphs
cites work: Directed Graphs Without Short Cycles
cites work: On directed triangles in digraphs
DOI: 10.1007/S00493-011-2589-4
Recommended article: Destroying longest cycles in graphs and digraphs
Recommended article: Cycle decompositions of complete digraphs
Recommended article: Decompositions of digraphs into paths and cycles
Recommended article: Cyclically decomposing the complete graph into cycles
Recommended article: Cycles in dense digraphs
Recommended article: Q4627526
Recommended article: Q5421810
Recommended article: Consistent cycles in graphs and digraphs
Recommended article: Decomposing various graphs into short even-length cycles
Recommended article: Q4726282
description: scientific article; zbMATH DE number 5990942