Node disjoint circuits in Eulerian digraphs
From Egres Open
Let G be a directed graph without oneway paralel arcs, in which every node has indegree and outdegree k. Is it true that there is a node v such that there are k directed cycles containing v, pairwise node-disjoint (except for v)?
Recently Wolfgang Mader [1] showed that the answer to the question is negative for any [math]k \geq 8[/math]. He also proved that the answer is positive for k=3, and for any k in vertex-transitive digraphs.
Remarks
This question was asked by Paul Seymour. Note that it would imply that if G is a digraph with at most kn nodes and every node has indegree and outdegree k, then there is a directed cycle of length at most n, which is a very interesting open special case of the Caccetta-Häggkvist conjecture.
