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 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 insure that P d,m ( G ) is satisfied are investigated. For example, if for fixed positive integers t ≥ 5, d ≥ 5 t 2 , and m ≥ 2, an m -connected graph G of order n satisfies the generalized degree condition δ t (G)≥( t (t+1) )( 5n (d+2) )+(m−1)d+3t 2 , then for n sufficientlylarge G has property P d, m ( G ). Also, if the order of magnitude of δ t ( G is decreased, then P d,m ( G ) will nothold; so the result is sharp in terms of order of magnitude of δ t ( G ). |
Year | DOI | Venue |
---|---|---|
1992 | 10.1016/0166-218X(92)90132-T | Discrete Applied Mathematics |
Keywords | Field | DocType |
generalized degree,menger path system | Has property,Integer,Discrete mathematics,Graph,Combinatorics,Disjoint sets,Vertex (geometry),Cardinality,Mathematics | Journal |
Volume | ISSN | Citations |
37-38, | Discrete Applied Mathematics | 2 |
PageRank | References | Authors |
0.59 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
R. J. Faudree | 1 | 174 | 38.15 |
R. J. Gould | 2 | 23 | 4.92 |
L. M. Lesniak | 3 | 44 | 8.23 |