A variation of Menger's theorem for long paths
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\).
- Generalized degrees and Menger path systems
- Wide diameter and minimum length of disjoint Menger path systems
- A Mengerian theorem for paths of length at least three
- scientific article; zbMATH DE number 4059450 (Why is no real title available?)
- Frames, \(A\)-paths, and the Erdős-Pósa property
- On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs
- Menger-type theorems with restrictions on path lengths
This page was built for publication: A variation of Menger's theorem for long paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q796549)
