Discussiones Mathematicae Graph Theory 15(2) (1995) 167-177
DOI: https://doi.org/10.7151/dmgt.1014

STRONGER BOUNDS FOR GENERALIZED DEGREES AND MENGER PATH SYSTEMS

Abstract

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  δ_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  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  δ_t(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  δ_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  P_d,m(G) will not, in general, hold; so the result is sharp in terms of the order of magnitude of  δ_t(G).

Keywords: generalized degree, Menger.

1991 Mathematics Subject Classification: 05C38.

References