|
This article is cited in 3 scientific papers (total in 3 papers)
Discrete mathematics and mathematical cybernetics
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
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$.
Keywords:
graph, diameter, diametral vertices, radius, metric ball and sphere, typical graphs, almost all graphs.
Received January 25, 2021, published April 2, 2021
Citation:
T. I. Fedoryaeva, “On radius and typical properties of $n$-vertex graphs of given diameter”, Sib. Èlektron. Mat. Izv., 18:1 (2021), 345–357
Linking options:
https://www.mathnet.ru/eng/semr1365 https://www.mathnet.ru/eng/semr/v18/i1/p345
|
Statistics & downloads: |
Abstract page: | 336 | Full-text PDF : | 95 | References: | 20 |
|