Standard

Asymptotic approximation for the number of n-vertex graphs of given diameter. / Fedoryaeva, T. I.

In: Journal of Applied and Industrial Mathematics, Vol. 11, No. 2, 01.04.2017, p. 204-214.

Research output: Contribution to journal › Article › peer-review

Harvard

Fedoryaeva, TI 2017, 'Asymptotic approximation for the number of n-vertex graphs of given diameter', Journal of Applied and Industrial Mathematics, vol. 11, no. 2, pp. 204-214. https://doi.org/10.1134/S1990478917020065

APA

Fedoryaeva, T. I. (2017). Asymptotic approximation for the number of n-vertex graphs of given diameter. Journal of Applied and Industrial Mathematics, 11(2), 204-214. https://doi.org/10.1134/S1990478917020065

Vancouver

Fedoryaeva TI. Asymptotic approximation for the number of n-vertex graphs of given diameter. Journal of Applied and Industrial Mathematics. 2017 Apr 1;11(2):204-214. doi: 10.1134/S1990478917020065

Author

Fedoryaeva, T. I. / Asymptotic approximation for the number of n-vertex graphs of given diameter. In: Journal of Applied and Industrial Mathematics. 2017 ; Vol. 11, No. 2. pp. 204-214.

BibTeX

@article{302d9affb86f41eb901bd82e7c7e21ac,
title = "Asymptotic approximation for the number of n-vertex graphs of given diameter",
abstract = "We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by F{\"u}redi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices.",
keywords = "graph, graph diameter, labeled graph, number of graphs, ordinary graph, shortest path",
author = "Fedoryaeva, {T. I.}",
year = "2017",
month = apr,
day = "1",
doi = "10.1134/S1990478917020065",
language = "English",
volume = "11",
pages = "204--214",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "2",

}

RIS

TY - JOUR

T1 - Asymptotic approximation for the number of n-vertex graphs of given diameter

AU - Fedoryaeva, T. I.

PY - 2017/4/1

Y1 - 2017/4/1

N2 - We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices.

AB - We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices.

KW - graph

KW - graph diameter

KW - labeled graph

KW - number of graphs

KW - ordinary graph

KW - shortest path

UR - http://www.scopus.com/inward/record.url?scp=85019662822&partnerID=8YFLogxK

U2 - 10.1134/S1990478917020065

DO - 10.1134/S1990478917020065

M3 - Article

AN - SCOPUS:85019662822

VL - 11

SP - 204

EP - 214

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

ER -

ID: 10043193