The extremal arc-count conjecture for strongly connected digraphs without acyclic separators
The extremal arc-count conjecture for strongly connected digraphs without acyclic separators
Let be a strongly connected digraph with vertices and arcs. An acyclic separator is a separator whose induced subdigraph is acyclic. Extremal arc-count conjecture. If does not have an acyclic separator, then
The digraph described in the surrounding text has arcs and is strongly -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.