Premium
Arc‐Disjoint Cycles and Feedback Arc Sets
Author(s) -
Florek Jan
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21742
Subject(s) - tournament , digraph , arc (geometry) , mathematics , disjoint sets , combinatorics , cardinality (data modeling) , feedback arc set , hamiltonian path , path (computing) , discrete mathematics , graph , computer science , geometry , voltage graph , line graph , data mining , programming language
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.