Menger-type theorems with restrictions on path lengths (Q687118)

Let \(u\) and \(v\) be non-adjacent vertices in a connected graph \(G\). A well-known result, Menger's theorem, says that the maximum number of point-disjoint paths joining \(u\) and \(v\) is equal to the minimum number of vertices whose deletion destroys all paths joining \(u\) and \(v\). The situation is changing when only paths not longer than a given constant are considered. Let \(\tau_ s(u,v)\) denote the minimum number of vertices meeting all \(u\)-\(v\)-paths not longer than \(s\) and \(\nu_ f(u,v)\) denote the maximum number of pairwise vertex-disjoint \(u\)-\(v\)- paths of length at most \(f\). It was proved, that for every \(s\) and \(t\) there is a positive integer \(f\) such that \(\tau_ s(u,v) \geq t\) implies \(\nu_ f(u,v) \geq t\). The minimal integer satisfying the above condition for all graphs is denoted \(f(s,t)\). The main object of the paper is estimating the value of \(f(s,t)\). The general upper bound for \(f(s,t)\) follows: \[ f(s,t)<{s+t-2 \choose s- 2}+{s+t-3 \choose s-2}. \] The lower bounds obtained by some constructions are: \[ f(s,t) \geq \lfloor {s \over t}-1 \rfloor^ t \quad \text{and } f(s,t) \geq {1 \over t} \lfloor {s-2 \over t}+1 \rfloor^ t. \] The case \(t=2\) is solved completely; it is shown that \(f(s,2)=\lfloor (s-1)^ 2/4 \rfloor+2\).