For positive integers d and m, let 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 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 . In this note, this result will be improved by obtaining corresponding results on property 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 will not, in general, hold; so the result is sharp in terms of the order of magnitude of δₜ(G).
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1014,
author = {R.J. Faudree and Zs. Tuza},
title = {Stronger bounds for generalized degrees and Menger path systems},
journal = {Discussiones Mathematicae Graph Theory},
volume = {15},
year = {1995},
pages = {167-177},
zbl = {0845.05061},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1014}
}
R.J. Faudree; Zs. Tuza. Stronger bounds for generalized degrees and Menger path systems. Discussiones Mathematicae Graph Theory, Tome 15 (1995) pp. 167-177. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1014/
[000] [CL] G. Chartrand and L. Lesniak, Graphs and Digraphs (Prindle Weber & Schmidt Boston 1986). | Zbl 0666.05001
[001] [FGL] R.J. Faudree, R.J. Gould and L. Lesniak, Generalized Degrees and Menger Path Systems, Discrete Applied Math. 37-38 (1992) 179-191, doi: 10.1016/0166-218X(92)90132-T.
[002] [FGS] R.J. Faudree, R.J. Gould and R.H. Schelp, Menger Path Systems, J. Combin. Math. Combin. Comp. 6 (1989) 9-21. | Zbl 0698.05051
[003] [FJOST] R.J. Faudree, M.S. Jacobson, E.T. Ordman, R.H. Schelp and Zs. Tuza, Menger's Theorem and Short Paths, J. Combin. Math. Combin. Comp. 2 (1987) 235-253. | Zbl 0649.05048
[004] [O] E.T. Ordman, Fault-tolerant Networks and Graph Connectivity, J. Combin. Math. Combin. Comp. 1 (1987) 191-205. | Zbl 0612.68060