RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2021, том 18, выпуск 1, страницы 345–357 (Mi semr1365)

Эта публикация цитируется в 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



Реферативные базы данных:


© МИАН, 2024