Center and its spectrum of almost all n-vertex graphs of given diameter

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\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.