| Abstract: | Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer dk(G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most dk(G). For a fixed positive integer d, some conditions to insure dk(G)≤d are given in this paper. In particular, if d≥3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s-1)k+1-d, then dk(G)≤d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. |
