ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

Discussiones Mathematicae Graph Theory


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


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


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.


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