Volume 20, No 1, 2013, P. 5876
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 nvertex 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 nvertex 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}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: tatiana.fedoryaeva@gmail.com
