The spanning eulerian subdigraph avoidance conjecture for semicomplete digraphs

Let kk be a non-negative integer. A semicomplete digraph is a directed graph in which every pair of distinct vertices is joined by at least one arc. A digraph is (k+1)(k+1)-arc-strong if deleting fewer than k+1k+1 arcs leaves it strongly connected. A spanning eulerian subdigraph is a subdigraph containing every vertex in which each vertex has equal indegree and outdegree.

Spanning eulerian subdigraph avoidance conjecture. Every (k+1)(k+1)-arc-strong semicomplete digraph DD has a spanning eulerian subdigraph that avoids any prescribed set of kk arcs.

The paper proves the existence of a finite connectivity bound, with an upper bound of (k+1)2/4+1(k+1)^2/4+1, while a degree-based obstruction gives the lower bound k+1k+1. The conjecture that the lower bound always suffices remains open.

Sources & referencesView supporting material

Primary source

Jørgen Bang-Jensen, Frédéric Havet and Anders Yeeo, “Spanning eulerian subdigraphs in semicomplete digraphs”, arXiv:1905.11019 (2019).

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.