|
Эта публикация цитируется в 3 научных статьях (всего в 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.
Поступила 25 января 2021 г., опубликована 2 апреля 2021 г.
Образец цитирования:
T. I. Fedoryaeva, “On radius and typical properties of $n$-vertex graphs of given diameter”, Сиб. электрон. матем. изв., 18:1 (2021), 345–357
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1365 https://www.mathnet.ru/rus/semr/v18/i1/p345
|
Статистика просмотров: |
Страница аннотации: | 335 | PDF полного текста: | 95 | Список литературы: | 20 |
|