DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

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

STRONGER BOUNDS FOR GENERALIZED DEGREES AND MENGER PATH SYSTEMS

R.J. Faudree

Department of Mathematical Sciences, University of Memphis,
Memphis, TN 38152, U.S.A.

Zs. Tuza

Computer and Automation Institute, Hungarian Academy of Sciences,
H-111 Budapest, Kende u. 13-17, Hungary

Abstract

For positive integers  d  and  m,  let  Pd,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  Pd,m(G)  is satisfied have been investigated. In particular, it has been shown, for fixed positive integers  t≥5,    d≥5t2,  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+3t2, then for  n  sufficiently large  G has property  Pd,m(G).  In this note, this result will be improved by obtaining corresponding results on property  Pd,m(G)  using a generalized degree condition  δt (G),  except that the restriction  d≥5t2 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  Pd,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

[CL] G. Chartrand and L. Lesniak, Graphs and Digraphs (Prindle Weber & Schmidt Boston 1986).
[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.
[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.
[O] E.T. Ordman, Fault-tolerant Networks and Graph Connectivity, J. Combin. Math. Combin. Comp. 1 (1987) 191-205.