# Stronger bounds for generalized degrees and Menger path systems

Discussiones Mathematicae Graph Theory (1995)

- Volume: 15, Issue: 2, page 167-177
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topR.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 -

## References

top- [CL] G. Chartrand and L. Lesniak, Graphs and Digraphs (Prindle Weber & Schmidt Boston 1986). Zbl0666.05001
- [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.
- [FGS] R.J. Faudree, R.J. Gould and R.H. Schelp, Menger Path Systems, J. Combin. Math. Combin. Comp. 6 (1989) 9-21. Zbl0698.05051
- [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. Zbl0649.05048
- [O] E.T. Ordman, Fault-tolerant Networks and Graph Connectivity, J. Combin. Math. Combin. Comp. 1 (1987) 191-205. Zbl0612.68060

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.