Volume 20, No 1, 2013, P. 58-76

UDC 519.1+519.173+519.176
Fedoryaeva T. I. 
Majorants and minorants in the graph class with given number of vertices and diameter

Abstract:
Majorants (minorants), i. e., extremal graphs such that for any i ≥ 0 exact upper (lower) estimates for the number of different balls of the radius i are attained at, are studied in the class of the n-vertex graphs with diameter d. For all parameters n and d, the minorants are described explicitly. It is found out when the majorants exist in the class of n-vertex graphs with diameter d, and the corresponding extremal graphs are described.
Il. 9, bibliogr. 8.

Keywords: graph, metric ball, radius of the ball, the number of balls, estimate of the number of balls, extremal graph.

Fedoryaeva Tatiana Ivanovna ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: tatiana.fedoryaeva@gmail.com