Home » Subject » Graph Theory » Directed Graphs

Ádám's Conjecture

Importance: High ✭✭✭
Author(s): Ádám, András
Subject: Graph Theory
» Directed Graphs
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.
add new comment