Node disjoint circuits in Eulerian digraphs

From Egres Open
Jump to: navigation, search

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)?

Solved b.jpg

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.


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.


  1. W. Mader, Existence of openly disjoint circuits through a vertex, Journal of Graph Theory 63 (2010), 93-105. DOI link.