Geodesic
Stronger bounds for generalized degrees and Menger path systems
Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 167-177

Voir la notice de l'article provenant de la source Library of Science

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).
Keywords: generalized degree, Menger 
Faudree, R.; Tuza, Zs. Stronger bounds for generalized degrees and Menger path systems. Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 167-177. http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a3/
@article{DMGT_1995_15_2_a3,
     author = {Faudree, R. and Tuza, Zs.},
     title = {Stronger bounds for generalized degrees and {Menger} path systems},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {167--177},
     year = {1995},
     volume = {15},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a3/}
}
TY  - JOUR
AU  - Faudree, R.
AU  - Tuza, Zs.
TI  - Stronger bounds for generalized degrees and Menger path systems
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1995
SP  - 167
EP  - 177
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a3/
LA  - en
ID  - DMGT_1995_15_2_a3
ER  - 
%0 Journal Article
%A Faudree, R.
%A Tuza, Zs.
%T Stronger bounds for generalized degrees and Menger path systems
%J Discussiones Mathematicae. Graph Theory
%D 1995
%P 167-177
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a3/
%G en
%F DMGT_1995_15_2_a3

[1] [CL] G. Chartrand and L. Lesniak, Graphs and Digraphs (Prindle Weber Schmidt Boston 1986).

[2] [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.

[3] [FGS] R.J. Faudree, R.J. Gould and R.H. Schelp, Menger Path Systems, J. Combin. Math. Combin. Comp. 6 (1989) 9-21.

[4] [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.

[5] [O] E.T. Ordman, Fault-tolerant Networks and Graph Connectivity, J. Combin. Math. Combin. Comp. 1 (1987) 191-205.