Volume 22, No 6, 2015, P. 43–54
UDC 519.1+519.173
T. I. Fedoryaeva
The diversity vector of balls of a typical graph of small diameter
Abstract:
For ordinary connected graphs, the diversity vectors of balls (ith component of the vector is equal to the number of different balls of radius i) are studied asymptotically. The asymptotic behavior of the number of graphs of small diameter with full diversity of balls is investigated. The diversity vector of balls of a typical graph of the given small diameter is calculated. Asymptotically exact value of the number of labeled n-vertex graphs of diameter 3 is obtained.
Ill. 2, bibliogr. 12.
Keywords: graph, metric ball, radius of ball, number of balls, diversity vector of balls, typical graph.
DOI: 10.17377/daio.2015.22.512
Tatiana I. Fedoryaeva 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: tatiana.fedoryaeva@gmail.com
Received 20 September 2015
Revised 26 October 2015
References
[1] A. A. Evdokimov, Locally isometric embeddings of graphs and the metric prolongation property, Sib. Zh. Issled. Oper., 1, No. 1, 5–12, 1994. Translated in A. D. Korshunov, ed., Discrete Analysis and Operations Research, pp. 7–14, Kluwer Acad. Publ., Dordrecht, 1996 (Math. Its Appl., Vol. 355).[2] A. A. Evdokimov, On an approach to the classification of graphs as metric spaces, in Tezisy dokladov XI Mezhdunarodnoi konferentsii po problemam teoreticheskoi kibernetiki (Abstr. XI Int. Conf. Probl. Theor. Cybern.), Ul’yanovsk, Russia, June 10–14, 1996, pp. 57–59, Izd. MGU, Moscow, 1996.
[3] A. A. Evdokimov and T. I. Fedoryaeva, On the problem of characterizing the diversity vectors of balls, Diskretn. Anal. Issled. Oper., 21, No. 1, 44–52, 2014. Translated in J. Appl. Ind. Math., 8, No. 2, 190–195, 2014.
[4] T. I. Fedoryaeva, Operations and isometric embeddings of graphs related to the metric prolongation property, Diskretn. Anal. Issled. Oper., 2, No. 3, 49–67, 1995. Translated in A. D. Korshunov, ed., Operations Research and Discrete Analysis, pp. 31–49, Kluwer Acad. Publ., Dordrecht, 1997 (Math.
Its Appl., Vol. 391).
[5] T. I. Fedoryaeva, Diversity of balls in the metric spaces of trees, Diskretn. Anal. Issled. Oper., Ser. 1, 12, No. 3, 74–84, 2005.
[6] T. I. Fedoryaeva, Diversity vectors of balls in graphs and estimates of the components of the vectors, Diskretn. Anal. Issled. Oper., 14, No. 2, 47–67, 2007. Translated in J. Appl. Ind. Math., 2, No. 3, 341–356, 2008.
[7] T. I. Fedoryaeva, Exact upper estimates of the number of different balls of given radius for graphs with fixed number of vertices and diameter, Diskretn. Anal. Issled. Oper., 16, No. 6, 74–92, 2009.
[8] T. I. Fedoryaeva, On the graphs with given diameter, number of vertices, and local diversity of balls, Diskretn. Anal. Issled. Oper., 17, No. 1, 65–74, 2010. Translated in J. Appl. Ind. Math., 5, No. 1, 44–50, 2011.
[9] T. I. Fedoryaeva, Majorants and minorants for the classes of graphs with fixed diameter and number of vertices, Diskretn. Anal. Issled. Oper., 20, No. 1, 58–76, 2013. Translated in J. Appl. Ind. Math., 7, No. 2, 153–165, 2013.
[10] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1969. Translated under the title Teoriya grafov, Mir, Moscow, 1973.
[11] B. Bollobás, Graph Theory: An Introductory Course, Springer-Verl., New York, 1979 (Grad. Text Math., Vol. 63).
[12] I. Tomescu, An asymptotic formula for the number of graphs having small diameter, Discrete Math., 156, No. 1–3, 219–228, 1996.
