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 ≥ 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 ≥ 3 almost all n-vertex graphs of diameter k have radius (Formula presented), 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 ≥ 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.

Cite: Fedoryaeva T.I.
ON RADIUS AND TYPICAL PROPERTIES OF n-VERTEX GRAPHS OF GIVEN DIAMETER
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2021. V.18. N1. P.345-357. DOI: 10.33048/semi.2021.18.024 WOS Scopus РИНЦ MathNet OpenAlex

Dates:

Submitted:	Jan 25, 2021
Published online:	Apr 2, 2021

Identifiers:

Web of science:	WOS:000641267200001
Scopus:	2-s2.0-85108805564
Elibrary:	46265216
MathNet:	rus/semr1365
OpenAlex:	W3199510654

Citing:

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

Altmetrics: