The spanning eulerian subdigraph avoidance conjecture for semicomplete digraphs
The spanning eulerian subdigraph avoidance conjecture for semicomplete digraphs
Let 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 -arc-strong if deleting fewer than 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 -arc-strong semicomplete digraph has a spanning eulerian subdigraph that avoids any prescribed set of arcs.
The paper proves the existence of a finite connectivity bound, with an upper bound of , while a degree-based obstruction gives the lower bound . 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
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.