On radius and typical properties of n-vertex graphs of given diameter

Abstract

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.