Diversity vectors of balls in graphs and estimates of the components of the vectors |
| |
Authors: | T I Fedoryaeva |
| |
Institution: | (1) Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia |
| |
Abstract: | The diversity vectors of balls are considered (the ith component of a vector of this kind is equal to the number of different balls of radius i) for the usual connected graphs and the properties of the components of the vectors are studied. The sharp upper and lower estimates are obtained for the number of different balls of a given radius in the n-vertex graphs (trees) and n-vertex trees (graphs with n ? 2d) of diameter d. It is shown that the estimates are precise in every graph regardless of the radius of balls. It is proven a necessary and sufficient condition is given for the existence of an n-vertex graph of diameter d with local (complete) diversity of balls. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|