Эта публикация цитируется в
3 статьях
Дискретная математика и математическая кибернетика
On radius and typical properties of $n$-vertex graphs of given diameter
T. I. Fedoryaeva Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Аннотация:
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$.
Ключевые слова:
graph, diameter, diametral vertices, radius, metric ball and sphere, typical graphs, almost all graphs.
УДК:
519.173+
519.175
MSC: 05C12+
05C80 Поступила 25 января 2021 г., опубликована
2 апреля 2021 г.
Язык публикации: английский
DOI:
10.33048/semi.2021.18.024