Mader's nonseparating dipath conjecture

Let kk and mm be positive integers, and let DD be a kk-connected digraph. Denote its minimum outdegree and indegree by δ+(D)\delta^+(D) and δ(D)\delta^-(D), and define its minimum semi-degree by

δ(D)=min{δ+(D),δ(D)}.\delta(D)=\min\{\delta^+(D),\delta^-(D)\}.

A dipath PP has order mm when it contains mm vertices, and κ(D)\kappa(D) denotes vertex-connectivity.

Mader's nonseparating dipath conjecture. If

δ(D)2k+m1,\delta(D)\geq 2k+m-1,

then DD has a dipath PP of order mm such that

κ(DV(P))k.\kappa(D-V(P))\geq k.

This is the digraph analogue of the nonseparating path conjecture. At the time of the paper, it had been verified only for m=1m=1, and for m=2m=2 with k=1k=1; the general assertion remains open.

Sources & referencesView supporting material

Primary source

Yingzhi Tian, Hong-Jian Lai, Liqiong Xu and Jixiang Meng, “Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs”, arXiv:1710.01883 (2017).

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.