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

Less than 1 year old · traced to

Let DD be a strongly connected digraph with n≥3n\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

m≥3n−3.m\geq 3n-3.

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

References

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.