Destroying cycles in digraphs

DOI10.1007/S00493-011-2589-4MaRDI QIDQ653984zbMATH OpenOpenAlexFDO

Authors Molly Dunkum, Peter Hamburger, Attila Pór

Publication date 20 December 2011

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-011-2589-4

zbMATH Keywords

acyclic, 3-free digraphcyclesdigraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

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)]).

Recommendations

• Destroying longest cycles in graphs and digraphs
• Cycle decompositions of complete digraphs
• Decompositions of digraphs into paths and cycles
• Cyclically decomposing the complete graph into cycles
• Cycles in dense digraphs
• On removable cycles in graphs and digraphs
• Cycle decompositions of complete graphs
• Consistent cycles in graphs and digraphs
• Decomposing various graphs into short even-length cycles
• Publication:4726282

Cites work

• Cycles in dense digraphs
• Directed graphs without short cycles
• On directed triangles in digraphs

Cited in

(4)

• On Sullivan's conjecture on cycles in 4-free and 5-free digraphs
• 3-free strong digraphs with the maximum size
• Turán number of 3-free strong digraphs with out-degree restriction
• Packing arc-disjoint cycles in oriented graphs

This page was built for publication: Destroying cycles in digraphs

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