Abstract: 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 > 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 > 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.

Cite: Fedoryaeva T.I.
CENTER AND ITS SPECTRUM OF ALMOST ALL n-VERTEX GRAPHS OF GIVEN DIAMETER
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2021. V.18. N1. P.511-529. DOI: 10.33048/semi.2021.18.037 WOS Scopus РИНЦ MathNet OpenAlex

Dates:

Submitted:	Mar 18, 2021
Published online:	May 18, 2021

Identifiers:

Web of science:	WOS:000651771100001
Scopus:	2-s2.0-85108846053
Elibrary:	46265228
MathNet:	rus/semr1377
OpenAlex:	W3200068933

Citing:

DB	Citing
Scopus	1
Web of science	1
Elibrary	1
OpenAlex	1

Altmetrics: