Geodesic
On radius and typical properties of $n$-vertex graphs of given diameter
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 345-357.

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

A property of graphs from a class under consideration is typical if almost all graphs from this class have the given property. Typical properties of the class of $n$-vertex graphs of a fixed diameter $k$ are studied. A family of embedded classes of typical $n$-vertex graphs of a given diameter $k\geq 3$, which possess a number of established metric properties, is constructed. Based on the typical properties of metric balls contained in the graph, the radius of almost all $n$-vertex graphs from the investigated classes is found. It is proved that for every fixed integer $k\geq 3$ almost all $n$-vertex graphs of diameter $k$ have radius $\lceil\frac{k}{2}\rceil$, while the radius of almost all graphs of diameter $k=1,2$ is equal to the diameter. All found typical properties of $n$-vertex graphs of a fixed diameter $k\geq 2$ are also typical for connected graphs of diameter at least $k$, as well as for graphs (not necessarily connected) containing the shortest path of length at least $k$.
Keywords: graph, diameter, diametral vertices, radius, metric ball and sphere, typical graphs, almost all graphs. 
@article{SEMR_2021_18_1_a14,
     author = {T. I. Fedoryaeva},
     title = {On radius and typical properties of $n$-vertex graphs of given diameter},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {345--357},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a14/}
}
TY  - JOUR
AU  - T. I. Fedoryaeva
TI  - On radius and typical properties of $n$-vertex graphs of given diameter
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 345
EP  - 357
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a14/
LA  - en
ID  - SEMR_2021_18_1_a14
ER  - 
%0 Journal Article
%A T. I. Fedoryaeva
%T On radius and typical properties of $n$-vertex graphs of given diameter
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 345-357
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a14/
%G en
%F SEMR_2021_18_1_a14
T. I. Fedoryaeva. On radius and typical properties of $n$-vertex graphs of given diameter. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 345-357. http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a14/

[1] Yu.D. Burtin, “On extreme metric parameters of a random graph. I: Asymptotic estimates”, Theory Probab. Appl., 19:4 (1975), 710–725 | DOI | MR | Zbl

[2] O.I. Melnikov, R.I. Tyshkevich, V.A. Emelichev, V.I. Sarvanov, Lectures on graph theory, B.I. Wissenschaftsverlag, Mannheim, 1994 | MR | Zbl

[3] T.I. Fedoryaeva, “Operations and isometric embeddings of graphs related to the metric extension property”, Oper. Research and Discrete Anal., 391 (1997), 31–49 | DOI | MR | Zbl

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

[5] T.I. Fedoryaeva, “Structure of the diversity vector of balls of a typical graph with given diameter”, Sib. Électron. Math. Izv., 13 (2016), 375–387 | MR | Zbl

[6] T.I. Fedoryaeva, “Asymptotic approximation for the number of n-vertex graphs of given diameter”, J. Appl. Ind. Math., 11:2 (2017), 204–214 | DOI | MR | Zbl

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

[8] W. Goddard, O.R. Oellerman, “Distance in graphs”, Structural analysis of complexnNetworks, ed. M. Dehmer, Birkhäuser, Basel, 2011, 49–72 | MR | Zbl

[9] R.L. Graham, D.E. Knuth, O. Patashnik, Concrete mathematics, Addison-Wesley, Amsterdam, 1994 | MR | Zbl

[10] F. Harary, Graph theory, Addison-Wesley, Mass. etc, 1969 | MR | Zbl

[11] J.W. Moon, L. Moser, “Almost all (0,1) matrices are primitive”, Stud. Sci. Math. Hung., 1 (1966), 153–156 | MR | Zbl

[12] P.A. Ostrand, “Graphs with specified radius and diameter”, Discrete Math., 4 (1973), 71–75 | DOI | MR | Zbl