Stronger bounds for generalized degrees and Menger path systems

R.J. Faudree, and Zs. Tuza. "Stronger bounds for generalized degrees and Menger path systems." Discussiones Mathematicae Graph Theory 15.2 (1995): 167-177. <http://eudml.org/doc/270398>.

@article{R1995,
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 δₜ(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).},
author = {R.J. Faudree, Zs. Tuza},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {generalized degree; Menger; Menger path systems; disjoint paths; generalized degree condition},
language = {eng},
number = {2},
pages = {167-177},
title = {Stronger bounds for generalized degrees and Menger path systems},
url = {http://eudml.org/doc/270398},
volume = {15},
year = {1995},
}

TY - JOUR
AU - R.J. Faudree
AU - Zs. Tuza
TI - Stronger bounds for generalized degrees and Menger path systems
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 2
SP - 167
EP - 177
AB - 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).
LA - eng
KW - generalized degree; Menger; Menger path systems; disjoint paths; generalized degree condition
UR - http://eudml.org/doc/270398
ER -