Volume 20, No 1, 2013, P. 58-76
Fedoryaeva T. I.
Majorants and minorants in the graph class with given number of vertices and diameter
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
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia