Arc‐Disjoint Cycles and Feedback Arc Sets

DOI10.1002/JGT.21742MaRDI QIDQ5417829zbMATH OpenOpenAlexFDO

Authors Jan Florek

Publication date 22 May 2014

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.5467

zbMATH Keywords

arc-disjoint cyclesfeedback arc setisaak conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Abstract: Isaak posed the following problem. Suppose $T$ is a tournament having a minimum feedback arc set which induces an acyclic digraph with a hamiltonian path. Is it true that the maximum number of arc-disjoint cycles in $T$ equals the cardinality of minimum feedback arc set of $T$? We prove that the answer to the problem is in the negative. Further, we study the number of arc-disjoint cycles through a vertex $v$ of the minimum out-degree in an oriented graph $D$. We prove that if $v$ is adjacent to all other vertices, then $v$ belongs to $delt{a}^{+}(D)$ arc-disjoint cycles.

Recommendations

• scientific article; zbMATH DE number 842022
• Minimal arc-sets spanning dicycles
• Arc-disjoint directed and undirected cycles in digraphs
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• The minimum feedback arc set problem and the acyclic disconnection for graphs
• scientific article; zbMATH DE number 219251
• ON DISJOINT CYCLES
• The Minimal Feedback Arc Set Problems^*
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• Arcwise connectedness of efficient sets

Cites work

• Graphs with forbidden subgraphs
• On Sets of Consistent Arcs in a Tournament
• On the maximum cardinality of a consistent set of arcs in a random tournament
• Tournaments as feedback arc sets

Cited in

(5)

• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• scientific article; zbMATH DE number 1990692 (Why is no real title available?)
• Complete classification of tournaments having a disjoint union of directed paths as a minimum feedback arc set
• scientific article; zbMATH DE number 2114681 (Why is no real title available?)
• The minimum feedback arc set problem and the acyclic disconnection for graphs

This page was built for publication: Arc‐Disjoint Cycles and Feedback Arc Sets

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