Menu
For positive integers \(d\) and \(m\), let \(P_{d,m}(G)\) denote the property that between each pair of vertices of the graph \(G\), there are \(m\) openly disjoint paths of length at most \(d\). A collection of such paths is called a \({Menger \; path \; system}\). Minimal conditions involving various combinations of the connectivity, minimal degree, sum of degrees, and unions of neighborhoods of pairs of nonadjacent vertices that insure the existence of Menger path systems are investigated. For example, if for fixed positive integers \(d \geq 2\) and \(m\), a graph \(G\) has order \(n\), connectivity \(k \geq m\), and minimal degree \(\delta > (n – (k – m + 1)(d – 2))/{2} + m – 2\), then \(G\) has property \(P_{d,m}(G)\) for \(n\). Also, if a graph \(G\) of order \(n\) satisfies \(NC(G) > {5n}/(d + 2) + 2m\), then \(P_{d,m}(G)\) is satisfied. (A graph \(G\) satisfies \(NC(G) \geq t\) if the union of the neighborhoods of each pair of nonadjacent vertices is at least \(t\).) Other extremal results related to Menger path systems are considered.