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/