Volume 17, No 1, 2010, P. 65-74

UDC 519.17
T. I. Fedoryaeva
On graphs with given diameter, number of vertices, and local diversity of balls

Abstract:
The $n$-vertex graphs with diameter $d$ and local $t$-diversity of balls, i.e. graphs having $n$ different balls of radius $i$ for every $i\leq t$, in connection with the characterization problem of the diversity vectors of balls of usual connected graphs are studied. For such graphs there exists a lower bound for the number of vertices, defined by the parameters $d$ and $t$. All graphs of the minimal possible order with diameter $d$ and local $t$-diversity of balls (full diversity of balls) are explicitly described up to isomorphism. Moreover, the diversity vector of balls is calculated for any such graph.
Ill. 4, bibl. 8.

Keywords: graph, diameter of the graph, metric ball, radius of the ball, number of balls, diversity vector of balls.

Fedoryaeva Tat’yana Ivanovna ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: stdd@academ.org