Arc‐Disjoint Cycles and Feedback Arc Sets |
| |
| Authors: | Jan Florek |
| |
| Institution: | INSTITUTE OF MATHEMATICS AND CYBERNETICS, UNIVERSITY OF ECONOMICS, POLAND |
| |
| 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. |
| |
| Keywords: | feedback arc set Isaak conjecture arc‐disjoint cycles 05C20 05C38 |
|
|
