A variation of Menger's theorem for long paths (Q796549): Difference between revisions

The authors prove a Mengerian theorem for long paths. For \(n\geq 2\) let us write \(<u,S,v>^ n_ D\) iff every uv-path in the digraph D of length greater or equal n has at least one point in S, \(S\subseteq V(D)\), \(u,v\in V(D)-S\). Let an (D,u,v) be the maximum number of interior disjoint uv-paths in D of length at least n and let \(a_ n(h)\) be the minimum value of \(a_ n\) (D,u,v) over all triples (D,u,v), where D is a digraph, u,\(v\in V(D)\), and \(<u,S,v>^ n_ D\) implies \(| S| \geq h\), then it is proved: \(\{h/3n-5\}\leq a_ n(h)\leq \{h/n-1\}.\) The same holds for simple graphs and for this the reviewer showed \(\{(h+2)/3\}\leq a_ 3(h)\) for \(h\geq 9\) and \(\{h/2\}=a_ 3(h)\) for 1\(\leq h\leq 8\).