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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom