Importance: High ✭✭✭
Author(s): Ádám, András
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 1st, 2013
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.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options