Geodesic
Structure of the diversity vector of balls of a typical graph with given diameter
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 375-387.

Voir la notice de l'article provenant de la source Math-Net.Ru

For labeled $n$-vertex graphs with fixed diameter $d\geq 1$, the diversity vectors of balls (the ith component of the vector is equal to the number of different balls of radius $i$) are studied asymptotically. An explicit description of the diversity vector of balls of a typical graph with given diameter is obtained. A set of integer vectors $\Lambda_{n,d}$ consisting of $\lfloor\frac{d-1}{2}\rfloor$ different vectors for $d\geq 5$ and a unique vector for $d5$ is found. It is proved that almost all labeled $n$-vertex graphs of diameter $d$ have the diversity vector of balls belonging to $\Lambda_ {n,d}$. It is established that this property is not valid after removing any vector from $\Lambda_ {n,d}$. A number of properties of a typical graph of diameter $d$ is proved. In particular, it is obtained that such a graph for $d\geq 3$ does not possess the local $2$-diversity of balls and at the same time has the local $1$-diversity of balls, but has the full diversity of balls if $d=1,2$.
Keywords: graph, labeled graph, metric ball, number of balls, diversity vector of balls, typical graph.
Mots-clés : distance 
@article{SEMR_2016_13_a60,
     author = {T. I. Fedoryaeva},
     title = {Structure of the diversity vector of balls of a typical graph with given diameter},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {375--387},
     publisher = {mathdoc},
     volume = {13},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a60/}
}
TY  - JOUR
AU  - T. I. Fedoryaeva
TI  - Structure of the diversity vector of balls of a typical graph with given diameter
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 375
EP  - 387
VL  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a60/
LA  - ru
ID  - SEMR_2016_13_a60
ER  - 
%0 Journal Article
%A T. I. Fedoryaeva
%T Structure of the diversity vector of balls of a typical graph with given diameter
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 375-387
%V 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a60/
%G ru
%F SEMR_2016_13_a60
T. I. Fedoryaeva. Structure of the diversity vector of balls of a typical graph with given diameter. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 375-387. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a60/

[1] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994

[2] A. A. Evdokimov, “Locally isometric embeddings of graphs and the metric prolongation property”, Discrete Anal. and Oper. Research, 1 (1995), 7–14; Sibirsk. Zhur. Issled. Oper., 1:1 (1994), 5–12 | MR | Zbl

[3] A. A. Evdokimov, T. I. Fedoryaeva, “On the problem of characterizing the diversity vectors of balls”, J. Appl. Ind. Math., 8:2 (2014), 190–195 | DOI | MR | Zbl

[4] T. I. Fedoryaeva, “Operations and isometric embeddings of graphs related to the metric prolongation property”, Oper. Research and Discrete Anal., 2:3 (1997), 31–49 ; Diskretn. Anal. Issled. Oper., 2:3 (1995), 49–67 | DOI | MR

[5] T. I. Fedoryaeva, “On the diversity of metrical balls in graphs”, Abstracts of XIV the Intern. Conference, Publ. MSU, 2005, 159 http://new.math.msu.su/department/dm/dmmc/CONF/14k_tez.pdf

[6] T. I. Fedoryaeva, “Diversity of balls in the metric spaces of trees”, Diskretn. Anal. Issled. Oper., 12:3 (2005), 74–84 | MR | Zbl

[7] T. I. Fedoryaeva, “Diversity vectors of balls in graphs and estimates of the components of the vectors”, J. Appl. Ind. Math., 2:3 (2008), 341–357 ; Diskretn. Anal. Issled. Oper., 14:2 (2007), 47–67 | DOI | MR | Zbl

[8] T. I. Fedoryaeva, “Exact upper estimates of the number of different balls of given radius in graphs with fixed number of vertices and diameter”, Diskretn. Anal. Issled. Oper., 16:6 (2009), 74–92 | MR | Zbl

[9] T. I. Fedoryaeva, “On the graphs with given diameter, number of vertices, and local diversity of balls”, J. Appl. Ind. Math., 5:1 (2011), 44–50 ; Diskretn. Anal. Issled. Oper., 17:1 (2010), 65–74 | DOI | MR | Zbl

[10] T. I. Fedoryaeva, “Diversity of balls in graphs with fixed number of vertices and diameter”, Probl. of Theoret. Cybern., Publ. NNSU, N. Novgorod, 2011, 491–495

[11] T. I. Fedoryaeva, “Majorants and minorants for the classes of graphs with fixed diameter and number of vertices”, J. Appl. Ind. Math., 7:2 (2013), 153–165 | DOI | MR | Zbl

[12] T. I. Fedoryaeva, “The diversity vector of balls of a typical graph of small diameter”, Diskretn. Anal. Issled. Oper., 22:6 (2015), 43–54 | DOI | MR

[13] T. I. Fedoryaeva, “On the diversity of balls of a typical graph with given diameter”, Appl. Discrete Math., 8 (2015), 127–128 | DOI

[14] T. I. Fedoryaeva, “Computing the diversity vectors of balls of a given graph”, Siber. Electr. Math. Reports, 13 (2016), 122–129 | DOI

[15] T. I. Fedoryaeva, “Asymptotic approximation for the number of $n$-vertex graphs with given diameter”, Abstracts of Intern. Conference and PhD-Master Sum. School on Graphs and Groups, Spectra and Symmetries, Novosibirsk, 2016 (to appear)

[16] Z. Füredi, Y. Kim, The number of graphs of given diameter, 2012, arXiv: 1204.4580v1 [math.CO]

[17] F. Harary, Graph Theory, Addison-Wesley, London, 1969 | MR | Zbl

[18] K. L. Rychkov, “Sufficient conditions for the existence of a graph with a given variety of balls”, J. Appl. Ind. Math., 1:3 (2007), 380–385 ; Diskretn. Anal. Issled. Oper., 13:1 (2006), 99–108 | DOI | MR | MR | Zbl

[19] K. L. Rychkov, “Conditions for the existence of a graph with given diameter, connectivity, and ball diversity vector”, J. Appl. Ind. Math., 3:1 (2009), 107–116 ; Diskretn. Anal. Issled. Oper., 14:4 (2007), 43–56 | DOI | MR | MR | Zbl