Connectivity-Preserving Paths in Antisymmetric Digraphs

Definitions and mathematical statement

An antisymmetric digraph has no pair of oppositely directed arcs between distinct vertices. The supplied statement does not explicitly specify the range of the connectivity parameter $k$, whether connectivity means strong vertex connectivity, or whether digraphs are finite, loopless, and without parallel arcs. The following is a precise candidate formulation under those conventions, with $k\geq 1$; these qualifications require confirmation against the cited source.

Let $D=(V,A)$ be a finite loopless digraph without parallel arcs. Write \[ \delta^+(D)=\min_{v\in V}|\{w\in V:(v,w)\in A\}|, \qquad \delta^-(D)=\min_{v\in V}|\{w\in V:(w,v)\in A\}|. \] For $S\subseteq V$, let $D-S$ be the induced digraph on $V\setminus S$. A digraph is strongly connected if every ordered pair of vertices is joined by a directed path. For a positive integer $k$, interpret $\kappa(D)\geq k$, or $k$-connectedness, as requiring $|V(D)|\geq k+1$ and strong connectivity of $D-X$ for every $X\subseteq V(D)$ with $|X|<k$.

Under these conventions, the supplied conjectural question is: for every integer $k\geq 1$, every integer $m\geq 0$, and every $k$-connected antisymmetric digraph $D$ satisfying \[ \delta^+(D)\geq\left\lfloor\frac{3k+1}{2}\right\rfloor+m, \qquad \delta^-(D)\geq\left\lfloor\frac{3k+1}{2}\right\rfloor+m, \] does there exist a directed path $P$ with distinct vertices $v_0,\ldots,v_{2m}$, with $(v_i,v_{i+1})\in A$ for $0\leq i<2m$, such that \[ \kappa\left(D-V(P)\right)\geq k? \] Here length counts arcs, so $P$ has $2m+1$ vertices. In particular, when $m=0$, the question asks for a single vertex whose deletion preserves the required connectivity. The conventions above are an explicit interpretation of the supplied excerpt, not additional hypotheses verified from the report.

Short English statement

The supplied question asks whether sufficiently large minimum in-degree and out-degree force an antisymmetric digraph to contain a directed path of length $2m$ whose vertex deletion preserves $k$-connectivity. The interpretation of connectivity, the range of $k$, and the graph conventions require confirmation. The supplied curation attributes the conjecture to Mader and labels it open; those claims have not been independently verified here.

Sources

• Local UnsolvedMath registry: supplied record with permanent ID $30001432$, source problem code catalogue entry, title "Connectivity-Preserving Paths in Antisymmetric Digraphs," in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2010 and no named proposer in its proposer field; its background and literature assessment attribute the conjecture to Mader.
• Supplied primary reference: Graph Theory (2010), Oberwolfach Reports, Report 11/2010, pp. 521--580, DOI 10.4171/owr/2010/11. https://doi.org/10.4171/owr/2010/11. The record labels the statement corrected_verified and reports that its mathematical content was checked against the official report, with notation, context, and question form normalized without changing the source-level claim. This is supplied verification metadata, not an independent verification here.
• Supplied literature reference: Tian--Lai--Xu--Meng, "oriented-tree cases" (the supplied descriptive label), DOI 10.1016/j.disc.2018.10.001. https://doi.org/10.1016/j.disc.2018.10.001.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open, identifies it as Mader's antisymmetric-digraph path conjecture, and states that the report presents it as unresolved while later work records only partial cases. This is supplied dated literature triage, not an independently verified assessment. The record expressly calls for independent verification of time-sensitive status and cited claims.