Stronger bounds for generalized degress and Menger path systems

For positive integers d and m, let Pd,m(G) denote the property that between each pair of vertices of the graph G , there are m internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δt(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that Pd,m(G) is satisfied have been investigated. In particular, it has been shown, for fixed positive integers t ≥ 5, d ≥ 5t, and m, that if an m-connected graph G of order n satisfies the generalized degree condition δt(G) > (t/(t + 1))(5n/(d + 2)) + (m − 1)d + 3t , then for n sufficiently large G has property Pd,m(G). In this note, this result will be improved by obtaining corresponding results on property Pd,m(G) using a generalized degree condition δt(G), except that the restriction d ≥ 5t will be replaced by the weaker restriction d ≥ max{5t + 28, t + 77}. Also, it will be shown, just as in the original result, that if the order of magnitude of δt(G) is decreased, then Pd,m(G) will not, in general, hold; so the result is sharp in terms of the order of magnitude of δt(G).