Stronger bounds for generalized degrees and Menger path systems

Faudree, R. ; Tuza, Zs.

Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 167-177

Résumé

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 internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(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 P_d,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 δₜ(G) > (t/(t+1))(5n/(d+2))+(m-1)d+3t², then for n sufficiently large G has property P_d,m(G). In this note, this result will be improved by obtaining corresponding results on property P_d,m(G) using a generalized degree condition δₜ(G), except that the restriction d ≥ 5t² will be replaced by the weaker restriction d ≥ max5t+28,t+77. Also, it will be shown, just as in the original result, that if the order of magnitude of δₜ(G) is decreased, then P_d,m(G) will not, in general, hold; so the result is sharp in terms of the order of magnitude of δₜ(G).

Détail

Keywords: generalized degree, Menger