Geodesic
Center and its spectrum of almost all $n$-vertex graphs of given diameter
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 511-529.

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

We study typical (valid for almost all graphs of a class under consideration) properties of the center and its spectrum (the set of centers cardinalities) for $n$-vertex graphs of fixed diameter $k$. The spectrum of the center of all and almost all $n$-vertex connected graphs is found. The structure of the center of almost all $n$-vertex graphs of given diameter $k$ is established. For $k= 1,2$ any vertex is central, while for $k\geq 3$ we identified two types of central vertices, which are necessary and sufficient to obtain the centers of almost all such graphs; in addition, centers of constructed typical graphs are found explicitly. It is proved that the center of almost all $n$-vertex graphs of diameter $k$ has cardinality $n-2$ for $k=3$, and for $k\geq 4$ the spectrum of the center is bounded by an interval of consecutive integers except no more than one value (two values) outside the interval for even diameter $k$ (for odd diameter $k$) depending on $k$. For each center cardinality value outside this interval, we calculated an asymptotic fraction of the number of the graphs with such a center. The realizability of the found cardinalities spectrum as the spectrum of the center of typical $n$-vertex graphs of diameter $k$ is established.
Keywords: graph, diameter, diametral vertices, radius, central vertices, center, spectrum of center, typical graphs, almost all graphs. 
@article{SEMR_2021_18_1_a16,
     author = {T. I. Fedoryaeva},
     title = {Center and its spectrum of almost all $n$-vertex graphs of given diameter},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {511--529},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a16/}
}
TY  - JOUR
AU  - T. I. Fedoryaeva
TI  - Center and its spectrum of almost all $n$-vertex graphs of given diameter
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 511
EP  - 529
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a16/
LA  - en
ID  - SEMR_2021_18_1_a16
ER  - 
%0 Journal Article
%A T. I. Fedoryaeva
%T Center and its spectrum of almost all $n$-vertex graphs of given diameter
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 511-529
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a16/
%G en
%F SEMR_2021_18_1_a16
T. I. Fedoryaeva. Center and its spectrum of almost all $n$-vertex graphs of given diameter. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 511-529. http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a16/

[1] F. Buckley, Z. Miller, P.J. Slater, “On graphs containing a given graph as a center”, J. Graph Theory, 5 (1981), 427–434 | DOI | MR | Zbl

[2] F. Buckley, “The central ratio of a graph”, Discrete Math., 38:1 (1982), 17–21 | DOI | MR | Zbl

[3] F. Buckley, M. Lewinter, “Graphs with all diametral paths through distant central nodes”, Math. Comput. Modelling, 17:11 (1993), 35–41 | DOI | MR | Zbl

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

[5] T.I. Fedoryaeva, “Operations and isometric embeddings of graphs related to the metric extension property”, Operations research and discrete analysis, Mathematics and its applications, 391, ed. Korshunov A. D., 1997, 31–49 | MR | Zbl

[6] 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

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

[8] T.I. Fedoryaeva, “On radius and typical properties of $n$-vertex graphs of given diameter”, Sib. Électron. Mat. Izv., 18 (2021), 345–357 | MR | Zbl

[9] W. Goddard, O.R. Oellerman, “Distance in graphs”, Structural analysis of complex networks, ed. M. Dehmer, Birkhäuser, Boston, 2011 | MR

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

[11] F. Harary, Graph theory, Addison-Wesley, London, 1969 | MR | Zbl

[12] Yanan Hu, Xingzhi Zhan, Possible cardinalities of the center of a graph, 2020, arXiv: 2009.05925 [math.CO]

[13] G.N. Kopylov, E.A. Timofeev, “Centers and radii of graphs”, Usp. Mat. Nauk, 32:6(198) (1977), 226 | MR | Zbl

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

[15] D. Mubayi, D.B. West, “On the number of vertices with specified eccentricity”, Graphs Comb., 16:4 (2000), 441–452 | DOI | MR | Zbl