The extremal arc-count conjecture for strongly connected digraphs without acyclic separators

Let DD be a strongly connected digraph with n3n\geq 3 vertices and mm arcs. An acyclic separator is a separator whose induced subdigraph is acyclic. Extremal arc-count conjecture. If DD does not have an acyclic separator, then

m3n3.m\geq 3n-3.

The digraph Cn\vec{C}_n^* described in the surrounding text has 3(n1)=3n33(n-1)=3n-3 arcs and is strongly 22-connected, neighborhood-cyclic, and has no acyclic separator, motivating the claimed sharp lower bound.

Sources & referencesView supporting material

Primary source

Thilo Hartel and Dieter Rautenbach, “Cyclic Neighborhoods in Digraphs”, arXiv:2607.26606 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.