login/create account
Conjecture Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.
The conjecture fails for multigraphs (multiple arcs are allowed). Counterexamples for multidigraphs have been given by Grinberg [G], Jirásek [J] and Thomassen [T].
Surprisingly, the conjecture remains open for tournaments.
Conjecture Every tournament that is not transitive has an arc whose reversal reduces the number of directed cycles.
Bibliography
*[A] A. Ádám, Problem 2. In Theory of Graphs and its Applications (M. Fiedler, ed.), 234. (1964) Publishing House of the Czechoslovak Academy of Sciences, Prague.
[G] E.Y. Grinberg, Examples of non-Ádám multigraphs (in Russian) Latv. Mat. Ezhegodnik, 31 (1988), pp. 128–138
[J] J. Jirásek, On a certain class of multidigraphs, for which reversal of no arc decreases the number of their cycles, Comment. Math. Univ. Carolinae, 28 (1987), pp. 185–189.
[T] C. Thomassen, Counterexamples to Ádám's conjecture on arc reversals in directed graphs, J. Combin. Theory Ser. B, 42 (1987), pp. 128–130.
* indicates original appearance(s) of problem.
Drupal
CSI of Charles University