Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 204-214
Volume 24, No 2, 2017, P. 68-86
UDC 519.1+519.175
T. I. Fedoryaeva
Asymptotic approximation for the number of $n$-vertex graphs of given diameter
Abstract:
We prove that, for fixed $k \ge 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.
Illustr. 3, bibliogr. 9.
Keywords: graph, labeled graph, shortest path, graph diameter, number of graphs, ordinary graph.
DOI: 10.17377/daio.2017.24.534
Tatiana I. Fedoryaeva 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: tatiana.fedoryaeva@gmail.com
Received 29 March 2016
Revised 4 July 2016
References
[1] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, Moscow, 1990 [Russian]. Translated under the title Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994.[2] T. I. Fedoryaeva, The diversity vector of balls of a typical graph of small diameter, Diskretn. Anal. Issled. Oper., 22, No. 6, 43–54, 2015 [Russian].
[3] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1969. Translated under the title Teoriya grafov, Mir, Moscow, 1973 [Russian].
[4] S. V. Yablonskii, Vvedenie v diskretnuyu matematiku (Introduction to Discrete Mathematics), Nauka, Moscow, 1986 [Russian].
[5] Z. Füredi and Y. Kim, The number of graphs of given diameter, 2012 (Cornell Univ. Libr. e-Print Archive, arXiv:1204.4580).
[6] Y. Kim, Problems in extremal combinatorics, Ph. D. Thesis, Univ. Ill. Urbana-Champaign, Urbana, Champaign, 2011.
[7] J. W. Moon and L. Moser, Almost all (0,1) matrices are primitive, Stud. Sci. Math. Hung., 1, 153–156, 1966.
[8] I. Tomescu, An asymptotic formula for the number of graphs having small diameter, Discrete Math., 156, No. 1–3, 219–228, 1996.
[9] I. Tomescu, Almost all graphs and h-hypergraphs have small diameter, Aus?tralas. J. Comb., 31, 313–323, 2005.
