2012/06/24 by Jan Florek, Florek, Jan
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1206.5467
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 δ+(D) arc-disjoint cycles.