A generalisation of the diameter of a graph |
| |
Authors: | Douglas D. Grant |
| |
Affiliation: | Department of Computer Science, Swinburne Institute of Technology, Hawthorn, Vic., Australia 3122 |
| |
Abstract: | We prove the following theorem. If G is a connected finite graph of order p, and S is a k-subset of V(G) (where k≥2), then there is a pair of vertices in S which are at a distance ≤2(p−1)/k if k does not divide p, and ≤2(p−1)/k + 1 otherwise. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|