On k -diameter of k -connected graphs |
| |
Authors: | Xu Junming and Xu Keli |
| |
Institution: | (1) Dept. of Math., Univ. of Science and Technology of China, 230026 Hefei |
| |
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 d
k
(G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d
k
(G). For a fixed positive integer d, some conditions to insure d
k
(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 d
k
(G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible.
Supported by NNSF of China (19971086). |
| |
Keywords: | 05C12 05C40 68M10 |
本文献已被 SpringerLink 等数据库收录! |
|